Submission #30820

#	Time	Username	Problem	Language	Result	Execution time	Memory
30820		zscoder	Cake (CEOI14_cake)	C++14	100 / 100	1523 ms	28988 KiB

cake

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef tree<ll,null_type,greater<ll>,rb_tree_tag,tree_order_statistics_node_update> pbds;

int a[250001];
int query[511111];
int tmpidx[511111];
int st[1000001];
bool used[250001];
vector<pair<char,pair<int,int> > > queries;

void build(int id, int l, int r)
{
	if(r-l<2)
	{
		st[id]=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(id*2,l,mid);
	build(id*2+1,mid,r);
	st[id]=max(st[id*2],st[id*2+1]);
}

void update(int id, int l, int r, int pos, int v)
{
	if(pos>=r||pos<l) return ;
	if(r-l<2)
	{
		st[id]=v;
		return ;
	}
	int mid=(l+r)>>1;
	update(id*2,l,mid,pos,v);
	update(id*2+1,mid,r,pos,v);
	st[id]=max(st[id*2],st[id*2+1]);
}

int querymax(int id, int l, int r, int ql, int qr)
{
	if(ql>=r||l>=qr) return -1;
	//cerr<<id<<' '<<l<<' '<<r<<' '<<ql<<' '<<qr<<' '<<st[id]<<'\n';
	if(ql<=l&&r<=qr) return st[id];
	int mid=(l+r)>>1;
	return max(querymax(id*2,l,mid,ql,qr),querymax(id*2+1,mid,r,ql,qr));
}

int queryr(int id, int l, int r, int ql, int qr, int v)
{
	if(ql>=r||l>=qr) return -1;
	if(r-l<2)
	{
		//cerr<<id<<' '<<l<<' '<<r<<' '<<ql<<' '<<qr<<' '<<v<<' '<<st[id]<<'\n';
		if(st[id]>=v) return l;
		else return -1;
	}
	int mid=(l+r)>>1;
	if(ql<=l&&r<=qr)
	{
		//cerr<<id<<' '<<l<<' '<<r<<' '<<ql<<' '<<qr<<' '<<v<<' '<<st[id*2+1]<<'\n';
		if(st[id*2+1]>=v)
		{
			return queryr(id*2+1,mid,r,ql,qr,v);
		}
		else
		{
			return queryr(id*2,l,mid,ql,qr,v);
		}
	}
	return max(queryr(id*2,l,mid,ql,qr,v),queryr(id*2+1,mid,r,ql,qr,v));
}	

int queryl(int id, int l, int r, int ql, int qr, int v)
{
	if(ql>=r||l>=qr) return 100000000;
	if(r-l<2)
	{
		if(st[id]>=v) return l;
		else return 100000000;
	}
	int mid=(l+r)>>1;
	if(ql<=l&&r<=qr)
	{
		if(st[id*2]>=v)
		{
			return queryl(id*2,l,mid,ql,qr,v);
		}
		else
		{
			return queryl(id*2+1,mid,r,ql,qr,v);
		}
	}
	return min(queryl(id*2,l,mid,ql,qr,v),queryl(id*2+1,mid,r,ql,qr,v));
}

int main()
{
	//ios_base::sync_with_stdio(0); cin.tie(0);
	int n,s;
	scanf("%d %d",&n,&s);
	s--;
	for(int i=0;i<n;i++)
	{
		scanf("%d",a+i);
		a[i]--;
	}
	int q; scanf("%d",&q);
	int upd=0;
	for(int i=0;i<q;i++)
	{
		char c; int pos;
		scanf(" %c %d",&c,&pos);
		pos--;
		if(c=='E')
		{
			int v; scanf("%d",&v);
			v--;
			tmpidx[i]=v;
			queries.pb(mp(c,mp(pos,v)));
		}
		else
		{
			queries.pb(mp(c,mp(pos,-1)));
		}
	}
	build(1,0,n);
	set<pair<int,int> > cur;
	for(int i=0;i<n;i++) cur.insert(mp(-a[i],i));
	for(int i = 0; i < q; i++)
	{
		char c = queries[i].fi;
		int pos = queries[i].se.fi;
		int v = queries[i].se.se;
		if(c=='E')
		{
			cur.erase(mp(-a[pos],pos));
			vector<ii> hold;
			int num = n + upd;
			for(int i = 0; i < v; i++)
			{
				ii tmp = (*cur.begin());
				cur.erase(cur.begin());
				tmp.fi=-num;
				a[tmp.se]=num;
				update(1,0,n,tmp.se,num);
				hold.pb(tmp);
				num--;
			}
			update(1,0,n,pos,num);
			a[pos]=num;
			hold.pb(mp(-num,pos));
			for(int i=0;i<hold.size();i++) cur.insert(hold[i]);
			upd++;
		}
		else
		{
			if(s==pos)
			{
				printf("0\n");
			}
			else if(s>pos)
			{
				int tmp = querymax(1,0,n,pos,s);
				int ridx = queryl(1,0,n,s+1,n,tmp);
				if(ridx>n) ridx=n;
				ridx--;
				printf("%d\n",ridx-pos);
			}
			else
			{
				int tmp = querymax(1,0,n,s+1,pos+1);
				int lidx = queryr(1,0,n,0,s,tmp);
				printf("%d\n",pos-1-lidx);
			}
		}		
	}
}

Compilation message (stderr)

cake.cpp: In function 'int main()':
cake.cpp:165:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<hold.size();i++) cur.insert(hold[i]);
                 ^
cake.cpp:113:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&s);
                      ^
cake.cpp:117:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",a+i);
                  ^
cake.cpp:120:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int q; scanf("%d",&q);
                       ^
cake.cpp:125:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c %d",&c,&pos);
                          ^
cake.cpp:129:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int v; scanf("%d",&v);
                         ^

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50