Submission #423060

#	Time	Username	Problem	Language	Result	Execution time	Memory
423060		MDario	The Big Prize (IOI17_prize)	C++11	20 / 100	116 ms	6748 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], abi1[200001];
    vector<int> v[200001];
    void update_abi(int xf, int yf){
        while(xf<=maxn){
            abi[xf]+=yf;
            abi1[xf]+=yf;
            xf+=xf&(-xf);
        }
        return;
    }
    void update_abi1(int xf, int yf){
        while(xf<=maxn){
            abi1[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_ab11(int xf){
        int cr=0;
        while(xf>0){
            cr+=abi1[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)-abi1[cr+(1<<i)]<xf){
                    cf+=(1<<i)-abi1[cr+(1<<i)];
                    cr+=(1<<i);
                }
            }
        }
        return cr;
    }
    int find_best(int n) {
        if(n<=4500){
            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 < 450; i++) {
                v[i]=ask(i);
                if(v[i][0]+v[i][1]==0)return i;
            }
            int x=0;
            for(int i = 0; i < 450; i++){
                x=max(x, v[i][0]+v[i][1]);
            }
            for(int i = 0; i < 450; i++){
                if(v[i][0]+v[i][1]!=x){
                    update_abi(i+1, 1);
                }
                else update_abi1(i+1, 1);
            }
            int l, r, z, c[20];
            for(int i=1; i*450<n; i++){
                l=i*450;
                r=min(l+450-1, n-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--;
                    }
                    else break;
                }
                if(l>r||v[r][0]==query_abi1(r+1))continue;
                update_abi1(r+1, 1);
                c[0]=v[r][0]-query_abi1(r);
                for(int t=0; t<c[0]; t++){
                    r--;
                    c[1]=l-query_ab11(l+1)+1;
                    c[3]=r-query_ab11(r+1)+1;
                    while(c[1]<=c[3]){
                        c[2]=(c[1]+c[3])/2;
                        c[4]=query_abi2(c[2]);
                        v[c[4]]=ask(c[4]);
                        if(v[c[4]][0]+v[c[4]][1]!=x){
                            update_abi(c[4]+1, 1);
                            if(v[c[4]][0]+v[c[4]][1]==0)return c[4];
                            break;
                        }
                        update_abi1(c[4]+1, 1);
                        if(v[c[4]][0]==query_abi1(c[4]+1))c[1]=c[2];
                        else c[3]=c[2]-1;
                    }
                }
            }
        }
    	return 0;
    }

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:76:23: warning: unused variable 'z' [-Wunused-variable]
   76 |             int l, r, z, c[20];
      |                       ^

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