Submission #423062

#	Time	Username	Problem	Language	Result	Execution time	Memory
423062		MDario	The Big Prize (IOI17_prize)	C++11	99.26 / 100	65 ms	5924 KiB

prize

    #include "prize.h"
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    #define F first
    #define S second
    int maxn, abi[200001];
    vector<int> v[200001];
    void update_abi(int xf, int yf){
        while(xf<=maxn){
            abi[xf]+=yf;
            xf+=xf&(-xf);
        }
        return;
    }
    int query_abi1(int xf){
        int cr=0;
        while(xf>0){
            cr+=abi[xf];
            xf-=xf&(-xf);
        }
        return cr;
    }
    int query_abi2(int xf){
        int cr=0, cf=0;
        for(int i=18; i>=0; i--){
            if(cr+(1<<i)<=maxn){
                if(cf+(1<<i)-abi[cr+(1<<i)]<xf){
                    cf+=(1<<i)-abi[cr+(1<<i)];
                    cr+=(1<<i);
                }
            }
        }
        return cr;
    }
    int find_best(int n) {
        if(n<=5000){
            for(int i = 0; i < n; i++) {
                vector<int> res = ask(i);
                if(res[0] + res[1] == 0)
                    return i;
            }
        }
        else{
            maxn=n;
            for(int i = 0; i < 500; i++) {
                v[i]=ask(i);
                if(v[i][0]+v[i][1]==0)return i;
            }
            int x=0, y=0;
            for(int i = 0; i < 500; i++){
                x=max(x, v[i][0]+v[i][1]);
            }
            y=x;
            for(int i = 0; i < 500; i++){
                if(v[i][0]+v[i][1]!=x){
                    y--;
                    update_abi(i+1, 1);
                }
            }
            int l, r, z, c[20];
            for(int i=1; i*500<n; i++){
                l=i*500;
                r=min(l+500-1, n-1);
                z=l-query_abi1(l+1)+1;
                while(l<=r){
                    v[r]=ask(r);
                    if(v[r][0]+v[r][1]!=x){
                        update_abi(r+1, 1);
                        if(v[r][0]+v[r][1]==0)return r;
                        r--;
                        y--;
                    }
                    else break;
                }
                if(l>r||v[r][0]==query_abi1(r+1))continue;
                c[0]=v[r][0]-query_abi1(r);
                for(int t=0; t<c[0]; t++){
                    r--;
                    c[1]=l;
                    c[3]=r;
                    while(c[1]<=c[3]){
                        c[2]=(c[1]+c[3])/2;
                        c[4]=query_abi2(c[2]-l+z);
                        if(v[c[4]].empty())v[c[4]]=ask(c[4]);
                        if(v[c[4]][0]+v[c[4]][1]!=x){
                            y--;
                            update_abi(c[4]+1, 1);
                            if(v[c[4]][0]+v[c[4]][1]==0)return c[4];
                            break;
                        }
                        if(v[c[4]][0]==query_abi1(c[4]+1))c[1]=c[2]+1;
                        else c[3]=c[2]-1;
                    }
                }
            }
        }
    	return 0;
    }

• Subtask 1: 20 / 20
• Subtask 2: 79.26 / 80