Submission #55316264

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
using ui = unsigned;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,l,r) for(int i=(l);i>=(r);--i)
#define repn(i,n) for(int i=0;i<(n);++i)
#define allc(x) (x).begin(),(x).end()
#define sizc(x) ((int)(x).size())
#define fir first
#define sec second
constexpr int N = 2e5+5;
int dx[]{0,1,1,1,0,-1,-1,-1,};
int dy[]{1,1,0,-1,-1,-1,0,1,};
int n;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;

using ui = unsigned;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,l,r) for(int i=(l);i>=(r);--i)
#define repn(i,n) for(int i=0;i<(n);++i)
#define allc(x) (x).begin(),(x).end()
#define sizc(x) ((int)(x).size())
#define fir first
#define sec second

constexpr int N = 2e5+5;

int dx[]{0,1,1,1,0,-1,-1,-1,};
int dy[]{1,1,0,-1,-1,-1,0,1,};

int n;
int x[N],y[N];
map<pair<int,int>,int> mp;

bool del[N];
int p[N];

vector<pair<int,int>> sg[N];
vector<int> vc[N];
struct fenwick{
    ll c[N];
    void add(int x,ll k){
        ++x;
        while(x<=2e5+1)c[x]+=k,x+=x&-x;
    }
    ll sum(int x){
        ++x;
        ll ret=0;
        while(x)ret+=c[x],x^=x&-x;
        return ret;
    }
}t1,t2;
void add(int x,ll k){
    t1.add(x,k),t2.add(x,x*k);
}
ll sum(int x){return t1.sum(x)*(x+1)-t2.sum(x);}

signed main(){
    #ifndef ONLINE_JUDGE
    freopen("sample.in","r",stdin);
    freopen("sample.out","w",stdout);
    #endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>n;
    rep(i,1,n)cin>>x[i]>>y[i],mp[{x[i],y[i]}]=i;
    iota(p+1,p+n+1,1);sort(p+1,p+n+1,[&](int a,int b){
        if(x[a]==x[b])return y[a]<y[b];
        return x[a]<x[b];
    });
    rep(i,1,n){
        int pos=p[i];
        if(del[pos])continue;
        int lst=3;
        int u=pos;
        vector<int> vt;
        set<array<int,3>> vis;
        while(true){
            vt.push_back(u);
            del[u]=1;
            int st=lst+5&7;
            bool ok=1;
            repn(i,8){
                int nx=x[u]+dx[i+lst+5&7],ny=y[u]+dy[i+lst+5&7];
                if(mp.count({nx,ny})){
                    if(vis.count(array<int,3>{x[u],y[u],i+lst+5&7})){ok=0;break;}
                    vis.insert(array<int,3>{x[u],y[u],i+lst+5&7});
                    if(y[u]!=ny)vc[min(y[u],ny)].push_back(min(x[u],nx));
                    lst=i+lst+5&7;
                    u=mp[{nx,ny}];
                    break;
                }
            }
            if(!ok)break;
        }
        for(auto j:vt)mp.erase({x[j],y[j]});
        int L=2e5,R=0;
        for(auto j:vt)L=min(L,y[j]),R=max(R,y[j]);
        rep(j,L,R){
            sort(allc(vc[j]));
            repn(k,sizc(vc[j])>>1)sg[j].emplace_back(vc[j][k*2],vc[j][k*2+1]);
        }
        rep(j,L,R)vc[j].clear();
    }
    ll ans=0;
    rep(i,0,2e5){
        vector<pair<int,int>> nw;
        sort(allc(sg[i]));
        int l=-1,r=-1;
        for(auto p:sg[i]){
            int L=p.fir,R=p.sec;
            if(L==R)continue;
            if(L>r){
                if(~l)nw.emplace_back(l,r);
                l=L,r=R;
            }
            else r=max(r,R);
        }
        if(~l)nw.emplace_back(l,r);
        sg[i]=nw;
    }
    rep(i,1,2e5){
        for(auto p:sg[i-1])add(p.fir,1),add(p.sec,-1);
        for(auto p:sg[i])ans+=sum(p.sec-1)-sum(p.fir-1);
        for(auto p:sg[i-1])add(p.fir,-1),add(p.sec,1);
    }
    cout<<ans<<'\n';
}

Submission Info

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:72:23: warning: suggest parentheses around ‘+’ in operand of ‘&’ [-Wparentheses]
   72 |             int st=lst+5&7;
      |                    ~~~^~
Main.cpp:75:37: warning: suggest parentheses around ‘+’ in operand of ‘&’ [-Wparentheses]
   75 |                 int nx=x[u]+dx[i+lst+5&7],ny=y[u]+dy[i+lst+5&7];
      |                                ~~~~~^~
Main.cpp:75:59: warning: suggest parentheses around ‘+’ in operand of ‘&’ [-Wparentheses]
   75 |                 int nx=x[u]+dx[i+lst+5&7],ny=y[u]+dy[i+lst+5&7];
      |                                                      ~~~~~^~
Main.cpp:77:62: warning: suggest parentheses around ‘+’ in operand of ‘&’ [-Wparentheses]
   77 |                     if(vis.count(array<int,3>{x[u],y[u],i+lst+5&7})){ok=0;break;}
      |                                                         ~~~~~^~
Main.cpp:78:60: warning: suggest parentheses around ‘+’ in operand of ‘&’ [-Wparentheses]
   78 |                     vis.insert(array<int,3>{x[u],y[u],i+lst+5&7});
      |                                                       ~~~~~^~
Main.cpp:80:30: warning: suggest parentheses around ‘+’ in operand of ‘&’ [-Wparentheses]
   80 |                     lst=i+lst+5&7;
      |                         ~~~~~^~
Main.cpp:72:17: warning: unused variable ‘st’ [-Wunused-variable]
   72 |             int st=lst+5&7;
      |                 ^~

Judge Result