求助,样例未过,AC on #1
查看原帖
求助,样例未过,AC on #1
770431
GavinCQTD楼主2024/12/21 12:05
/******************************
  @GavinCQTD / 2024-12-19 16:34:24
  "P1856 [IOI1998] [USACO5.5] 矩形周长Picture" From Luogu
  # https://www.luogu.com.cn/problem/P1856
  1000 ms / 125 MB
******************************/
/* We all make choices, but in the end our choices make us. */

// #pragma GCC optimize(1,2,3,"Ofast","inline")

// #define NDEBUG

#include <iostream>
#include <algorithm>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <unordered_map>
using namespace std;
inline void pass(){return;}
inline void hold(){while(1);}
#define endl "\n"
#define mp(a,b) make_pair(a,b)
#define ct(a) while(!a.empty()) a.pop()
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
#define cdb cerr<<"Debug: "
#define cwn cerr<<"Warn: "
#define debug(x) cerr<<"In Line "<<__LINE__<<": "<<#x<<" = "<<x<<"\n"
#define sp(a) fixed<<setprecision(a)
#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
#define ll long long
#define ull unsigned long long
#define ld long double
// #define int ll
// #define _debug

int _t,n,_xb=0,_yb=0,tree[300005],lzy[300005],ans=0;
struct jx{
    int x1,y1,x2,y2;
}js[100005];
struct bx{
    int x,y1,y2,tp;
}xb[300005];
struct by{
    int y,x1,x2,tp;
}yb[300005];

bool cmpx(bx x,bx y){
    if(x.x==y.x) return x.tp<y.tp;
    return x.x<y.x;
}
bool cmpy(by x,by y){
    if(x.y==y.y) return x.tp<y.tp;
    return x.y<y.y;
}

inline void pushup(int u){tree[u]=tree[u*2]+tree[u*2+1];}
inline bool inrange(int l,int r,int ql,int qr){return (ql<=l)&&(r<=qr);}
inline bool outofrange(int l,int r,int ql,int qr){return (l>qr)||(r<ql);}
inline void maketag(int u,int ul,int ur,int uk){
    lzy[u] += uk;
    tree[u] += (ur-ul+1)*uk;
}
inline void pushdown(int u,int ul,int ur){
    int mid=(ul+ur)>>1;
    maketag(u*2,ul,mid,lzy[u]);
    maketag(u*2+1,mid+1,ur,lzy[u]);
    lzy[u] = 0;
}
int query(int u,int l,int r,int ql,int qr){
    if(inrange(l,r,ql,qr)) return tree[u];
    else if(!outofrange(l,r,ql,qr)){
        int mid=(l+r)>>1;
        pushdown(u,l,r);
        return query(u*2,l,mid,ql,qr)+query(u*2+1,mid+1,r,ql,qr);
    }
    else return 0;
}
void update(int u,int l,int r,int ul,int ur,int uk){
    if(inrange(l,r,ul,ur)) maketag(u,l,r,uk);
    else if(!outofrange(l,r,ul,ur)){
        int mid=(l+r)>>1;
        pushdown(u,l,r);
        update(u*2,l,mid,ul,ur,uk);
        update(u*2+1,mid+1,r,ul,ur,uk);
        pushup(u);
    }
}

void solve(int testID){
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> js[i].x1 >> js[i].y1 >> js[i].x2 >> js[i].y2;
        xb[++_xb] = {js[i].x1,js[i].y1,js[i].y2-1,0};
        xb[++_xb] = {js[i].x2,js[i].y1,js[i].y2-1,0};
        xb[++_xb] = {js[i].x2,js[i].y1,js[i].y2-1,1};
        yb[++_yb] = {js[i].y1,js[i].x1,js[i].x2-1,0};
        yb[++_yb] = {js[i].y2,js[i].x1,js[i].x2-1,0};
        yb[++_yb] = {js[i].y2,js[i].x1,js[i].x2-1,1};
    }
    sort(xb+1,xb+_xb+1,cmpx);
    int lst=0;
    for(int i=1;i<=_xb;i++){
        if(xb[i].tp){
            update(1,-1e4,1e4,xb[i].y1,xb[i].y2,-2);
            lst = query(1,-1e4,1e4,-1e4,1e4);
            continue;
        }
        update(1,-1e4,1e4,xb[i].y1,xb[i].y2,1);
        int qres=query(1,-1e4,1e4,-1e4,1e4);
        ans += qres-lst;
        // cerr << ">>> " << i << " " << lst << " " << qres << " " << ans << "\n";
        lst = qres;
    }
    // debug(ans);
    memset(tree,0,sizeof(tree));
    memset(lzy,0,sizeof(lzy));
    sort(yb+1,yb+_yb+1,cmpy);
    lst = 0;
    for(int i=1;i<=_yb;i++){
        if(yb[i].tp){
            update(1,-1e4,1e4,yb[i].x1,yb[i].x2,-2);
            lst = query(1,-1e4,1e4,-1e4,1e4);
            continue;
        }
        update(1,-1e4,1e4,yb[i].x1,yb[i].x2,1);
        int qres=query(1,-1e4,1e4,-1e4,1e4);
        ans += qres-lst;
        // cerr << ">>> " << i << " " << lst << " " << qres << " " << ans << "\n";
        lst = qres;
    }
    cout << ans;
    // debug(ans);
    // cerr << "--------------------------------\n";
    // for(int i=1;i<=_xb;i++) cerr<<xb[i].x<<" "<<xb[i].y1<<" "<<xb[i].y2<<" "<<xb[i].tp<<"\n";
    // cerr << "--------------------------------\n";
    // for(int i=1;i<=_yb;i++) cerr<<yb[i].y<<" "<<yb[i].x1<<" "<<yb[i].x2<<" "<<xb[i].tp<<"\n";
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    // freopen("PublicDebug.debug", "w", stderr);

    // cout << sp();
    // cerr << sp();

    _t = 1;
    // cin >> _t;

    for(int ran=0;ran<_t;ran++) solve(ran);

    fflush(stdout);
    return 0;
}

样例输出了 356

2024/12/21 12:05
加载中...