Submission #55316264
Source Code Expand
Copy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
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
2024-07-06 13:39:04
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
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