Submission #55316264


Source Code Expand

Copy
#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

Submission Time
Task G - Go Territory
User KnownError_
Language C++ 20 (gcc 12.2)
Score 0
Code Size 3144 Byte
Status WA
Exec Time 4431 ms
Memory 266720 KB

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

Set Name Sample All
Score / Max Score 0 / 0 0 / 600
Status
AC × 2
WA × 1
AC × 4
WA × 6
TLE × 18
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, sample_01.txt, sample_02.txt, sample_03.txt, test_00.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt
Case Name Status Exec Time Memory
random_01.txt WA 210 ms 23992 KB
random_02.txt WA 211 ms 23976 KB
random_03.txt WA 206 ms 23712 KB
random_04.txt TLE 4419 ms 149400 KB
random_05.txt TLE 4420 ms 149168 KB
random_06.txt TLE 4420 ms 149092 KB
random_07.txt TLE 4419 ms 83636 KB
random_08.txt TLE 4419 ms 83656 KB
random_09.txt AC 245 ms 43028 KB
random_10.txt AC 246 ms 42800 KB
random_11.txt TLE 4420 ms 149136 KB
random_12.txt TLE 4421 ms 149132 KB
random_13.txt TLE 4421 ms 149896 KB
random_14.txt TLE 4424 ms 149572 KB
random_15.txt TLE 4422 ms 149412 KB
random_16.txt WA 370 ms 49316 KB
random_17.txt WA 363 ms 48904 KB
random_18.txt TLE 4420 ms 149124 KB
random_19.txt TLE 4420 ms 149336 KB
random_20.txt TLE 4420 ms 149132 KB
sample_01.txt AC 6 ms 8352 KB
sample_02.txt AC 6 ms 8136 KB
sample_03.txt WA 6 ms 8392 KB
test_00.txt TLE 4431 ms 245260 KB
test_01.txt TLE 4426 ms 266492 KB
test_02.txt TLE 4426 ms 266256 KB
test_03.txt TLE 4425 ms 266720 KB
test_04.txt TLE 4428 ms 265848 KB


2025-03-18 (Tue)
21:52:51 +00:00