제출 #422945

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
422945		MDario	커다란 상품 (IOI17_prize)	C++11	20 / 100	108 ms	6028 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 < 448; 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 < 448; i++){
            x=max(x, v[i][0]+v[i][1]);
        }
        y=x;
        for(int i = 0; i < 448; 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*448<n; i++){
            l=i*448;
            r=min(l+448-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);
                    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: 0 / 80