Submission #228103

#	Time	Username	Problem	Language	Result	Execution time	Memory
228103		stefanbalaz2	ČVENK (COI15_cvenk)	C++14	0 / 100	3089 ms	204168 KiB

cvenk

/*



*/
#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;
}

Compilation message (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);
         ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 17
• Subtask 2: 0 / 21
• Subtask 3: 0 / 22
• Subtask 4: 0 / 40