이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*
*/
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define ll long long
typedef pair<ll,ll> pii;
typedef pair<pii,pii> ppp;
const int maxn=1e9-1;
ppp nula_ppp={{0,0},{0,0}};
ll rez;
map<ppp,ppp>dp;
typedef map<ppp,ppp>::iterator mitp;
int maxr,n;
int get_tip(ppp b,int x,int y){
int up=b.ff.ff;
int down=b.ff.ss;
int left=b.ss.ff;
int right=b.ss.ss;
if(x<=(up+down)/2){
if(y<=(left+right)/2)return 1;
else return 2;
}
else{
if(y<=(left+right)/2)return 3;
else return 4;
}
}
ppp new_bounds(ppp b,int x,int y){
int up=b.ff.ff;
int down=b.ff.ss;
int left=b.ss.ff;
int right=b.ss.ss;
if(x<=(up+down)/2)b.ff.ss=(up+down)/2;
else b.ff.ff=(up+down)/2+1;
if(y<=(left+right)/2)b.ss.ss=(left+right)/2;
else b.ss.ff=(left+right)/2+1;
return b;
}
ppp add(ppp a,ppp b){
a.ff.ff+=b.ff.ff;
a.ff.ss+=b.ff.ss;
a.ss.ff+=b.ss.ff;
a.ss.ss+=b.ss.ss;
return a;
}
ppp update(ppp b,int x,int y){
int up=b.ff.ff;
int down=b.ff.ss;
int left=b.ss.ff;
int right=b.ss.ss;
int tip=get_tip(b,x,y);
ppp ret=nula_ppp;
ret.ss.ss=1;
int len=(right-left+1)/2;
if(len*2<=2){
if(tip==1){
ret.ff.ff=0;
ret.ff.ss=1;
ret.ss.ff=1;
}
else if(tip==2){
ret.ff.ff=1;
ret.ff.ss=0;
ret.ss.ff=2;
}
else if(tip==3){
ret.ff.ff=1;
ret.ff.ss=2;
ret.ss.ff=0;
}
mitp it=dp.find(b);
if(it==dp.end())dp[b]=nula_ppp;
it=dp.find(b);
it->ss=add(it->ss,ret);
///printf("%d %d %d %d || %lld %lld %lld BLABLA\n",up,down,left,right,ret.ff.ff,ret.ff.ss,ret.ss.ff);
return ret;
}
ppp b2=new_bounds(b,x,y);
ppp pom=update(b2,x,y);
if(tip==1){
ret.ff.ff=pom.ff.ff;
ret.ff.ss=pom.ff.ss+len;
ret.ss.ff=pom.ss.ff+len;
}
else if(tip==2){
ret.ff.ff=pom.ff.ff+len;
ret.ff.ss=pom.ff.ss;
ret.ss.ff=pom.ff.ff+3*len-1;
}
else if(tip==3){
ret.ff.ff=pom.ff.ff+len;
ret.ff.ss=pom.ff.ff+3*len-1;
ret.ss.ff=pom.ss.ff;
}
mitp it=dp.find(b);
if(it==dp.end())dp[b]=nula_ppp;
it=dp.find(b);
it->ss=add(it->ss,ret);
/// printf("%d %d %d %d || %lld %lld %lld \n",up,down,left,right,ret.ff.ff,ret.ff.ss,ret.ss.ff);
return ret;
}
ppp get_block(ppp b){
if(dp.find(b)==dp.end())return nula_ppp;
return dp[b];
}
void go(ppp b,ll unode,ll dnode,ll lnode,ll rnode,ll sum){
int up=b.ff.ff;
int down=b.ff.ss;
int left=b.ss.ff;
int right=b.ss.ss;
ll len=(down-up+1);
mitp it=dp.find(b);
if(it==dp.end())return;
rez=min(rez,sum+unode+lnode+rnode*len+dnode*len+it->ss.ff.ff);
rez=min(rez,sum+unode*len+lnode*len+rnode+dnode*(len*2-1)+it->ss.ff.ss);
rez=min(rez,sum+unode*len+lnode*len+rnode*(len*2-1)+dnode+it->ss.ss.ff);
///printf("%d %d || %lld %lld AAA\n",up,down,it->ss.ss.ff,sum);
if(len<=2)return;
ppp b1=get_block(new_bounds(b,up,left));
ppp b2=get_block(new_bounds(b,up,right));
ppp b3=get_block(new_bounds(b,down,left));
ll len2=len/2;
go(new_bounds(b,up,left),unode,dnode+b3.ss.ss,lnode,rnode+b2.ss.ss,sum+dnode*len2+rnode*len2+b2.ff.ff+b3.ff.ff);
go(new_bounds(b,up,right),0,0,lnode+unode+dnode+b1.ss.ss+b3.ss.ss,rnode,sum+dnode*(len2*3-1)+unode*len2+lnode*len2+b1.ff.ss+b3.ff.ff+b3.ss.ss*(2*len2-1));
go(new_bounds(b,down,left),unode+b1.ss.ss+b2.ss.ss,dnode,0,0,sum+lnode*len2+unode*len2+rnode*(3*len2-1)+b1.ss.ff+b2.ff.ff+b2.ss.ss*(len2*2-1));
}
int main(){
///freopen("test.txt","r",stdin);
maxr=1;
while(maxr<maxn)maxr*=2;
maxr--;
scanf("%d",&n);
for(int i=1;i<=n;i++){
int x,y;
scanf("%d %d",&x,&y);
update((ppp){{0,maxr},{0,maxr}},x,y);
}
///ppp b=(ppp){{0,maxr},{0,maxr}};
///printf("%lld %lld %lld %lld\n",dp[b].ff.ff,dp[b].ff.ss,dp[b].ss.ff,dp[b].ss.ss);
rez=1e18;
go((ppp){{0,maxr},{0,maxr}},0,0,0,0,0);
cout<<rez<<endl;
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
cvenk.cpp: In function 'ppp update(ppp, int, int)':
cvenk.cpp:60:9: warning: unused variable 'up' [-Wunused-variable]
int up=b.ff.ff;
^~
cvenk.cpp:61:9: warning: unused variable 'down' [-Wunused-variable]
int down=b.ff.ss;
^~~~
cvenk.cpp: In function 'int main()':
cvenk.cpp:170:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
cvenk.cpp:173:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&x,&y);
~~~~~^~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |