Submission #1203879

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203879		nikolashami	The Big Prize (IOI17_prize)	C++20	0 / 100	1063 ms	6564 KiB

prize

#include<bits/stdc++.h>
using namespace std;
using ll=int;

#include"prize.h"
const ll L=475,N=2e5+2;

map<ll,ll>C;
map<array<ll,2>,array<ll,2>>mp;
ll x,lik,br,l,r,n;

struct node{
    ll lz=-1,s=0;
}st[4*N];

void push(int i,int l,int r){
    if (st[i].lz!=-1) {
        int m=(l+r)/2;
        st[2*i].s=st[i].lz*(m-l+1),st[2*i+1].s=st[i].lz*(r-m);
        st[2*i].lz=st[2*i+1].lz=st[i].lz;
        st[i].lz=-1;
    }
}

void upd(int l,int r,int x,int i=1,int l2=0,int r2=n-1){
    if(l<=l2&&r2<=r){
        st[i].s=x*(r2-l2+1),st[i].lz=x;
        return;
    }
    push(i,l2,r2);
    int m2=(l2+r2)/2;
    if(l<=m2)upd(l,r,x,2*i,l2,m2);
    if(m2+1<=r)upd(l,r,x,2*i+1,m2+1,r2);
    st[i].s=st[2*i].s+st[2*i+1].s;
}

int get(int l,int r,int i=1,int l2=0,int r2=n-1){
    if(l<=l2&&r2<=r)return st[i].s;
    push(i,l2,r2);
    int m2=(l2+r2)/2,S=0;
    if(l<=m2)S+=get(l,r,2*i,l2,m2);
    if(m2+1<=r)S+=get(l,r,2*i+1,m2+1,r2);
    return S;
}

vector<int>askk(int aa){
	ll G=get(aa,aa);
	if(G){
		G-=L;
		mp[{G,x-G}][0]=min(mp[{G,x-G}][0],aa);
		mp[{G,x-G}][1]=max(mp[{G,x-G}][1],aa);
		upd(mp[{G,x-G}][0],mp[{G,x-G}][1],G+L);
		return{G,x-G};
	}
	vector<int>a=ask(aa);
	if(a[0]+a[1]!=x)return a;
	G=a[0];
	mp[{G,x-G}][0]=min(mp[{G,x-G}][0],aa);
	mp[{G,x-G}][1]=max(mp[{G,x-G}][1],aa);
	upd(mp[{G,x-G}][0],mp[{G,x-G}][1],G+L);
	return{G,x-G};
}

int find_best(int NN){
	n=NN;
	for(int i=0;i<=4*NN;++i)
		st[i]={-1,0};
	mp.clear();
	C.clear();
	for(int i=0;i<L;++i){
		vector<int>a=askk(i);
		++C[a[0]+a[1]];
		if(!a[0]&&!a[1])return i;
	}
	x=0,lik=L-1;
	for(auto[u,v]:C)x=max(x,u);
	br=L-C[x];
	while(1){
		l=lik+1,r=n-1;
		while(l<=r){
			ll m=(l+r)/2;
			vector<int>a=askk(m);
			if(!a[0]&&!a[1])return m;
			else if(a[0]+a[1]==x){
				if(a[0]!=br)r=m-1;
				else l=m+1;
			}else{
				lik=m;
				r=m-1;
			}
		}
		++br;
	}
	return -1;
}

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