oj.uz

Submission #30816

# Submission time Handle Problem Language Result Execution time Memory
30816 2017-07-27T03:54:31 Z zscoder Cake (CEOI14_cake) C++14
0 / 100
 986 ms 47984 KB 
#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 st[1000001];

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;
	cin>>n>>s;
	s--;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		a[i]--;
	}
	int q; cin>>q;
	int upd=0;
	for(int i=0;i<q;i++)
	{
		char c; int pos;
		cin>>c>>pos;
		pos--;
		if(c=='E')
		{
			int v; cin>>v;
			v--;
			upd++;
			queries.pb(mp(c,mp(pos,v)));
		}
		else
		{
			queries.pb(mp(c,mp(pos,-1)));
		}
	}
	pbds global;
	for(int i = 0; i < n+upd; i++) global.insert(i);
	for(int i = q - 1; i >= 0; i--)
	{
		int v = queries[i].se.se;
		if(queries[i].fi=='E')
		{
			//take the v-th largest element
			queries[i].se.se = (*global.find_by_order(v));
			global.erase(queries[i].se.se);
		}
	}
	for(int i = 0; i < n; i++)
	{
		a[i] = (*global.find_by_order(n-1-a[i]));
		//cerr<<a[i]<<' ';
	}
	//cerr<<'\n';
	build(1,0,n);
	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')
		{
			update(1,0,n,pos,v);
			a[pos]=v;
		}
		else
		{
			if(s==pos)
			{
				cout<<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--;
				//[pos+1,ridx];
				//cerr<<"L : "<<s<<' '<<pos<<' '<<tmp<<' '<<ridx<<'\n';
				cout<<ridx-pos<<'\n';
			}
			else
			{
				int tmp = querymax(1,0,n,s+1,pos+1);
				int lidx = queryr(1,0,n,0,s,tmp);
				//[lidx+1,pos-1];
				//cerr<<"R : "<<s<<' '<<pos<<' '<<tmp<<' '<<lidx<<'\n';
				cout<<pos-1-lidx<<'\n';
			}
		}
		/*
		for(int j=0;j<n;j++)
		{
			cerr<<a[j]<<' ';
		}
		cerr<<'\n';
		*/
	}
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9068 KB Output is correct
2 Incorrect 0 ms 9068 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 813 ms 46928 KB Output isn't correct
2 Correct 846 ms 47060 KB Output is correct
3 Correct 839 ms 47060 KB Output is correct
4 Correct 769 ms 47060 KB Output is correct
5 Incorrect 899 ms 47984 KB Output isn't correct
6 Correct 883 ms 47984 KB Output is correct
7 Correct 829 ms 47984 KB Output is correct
8 Correct 813 ms 47984 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 159 ms 16844 KB Execution killed because of forbidden syscall writev (20)
2 Runtime error 109 ms 16844 KB Execution killed because of forbidden syscall writev (20)
3 Runtime error 99 ms 16844 KB Execution killed because of forbidden syscall writev (20)
4 Incorrect 0 ms 9068 KB Output isn't correct
5 Runtime error 533 ms 26216 KB Execution killed because of forbidden syscall writev (20)
6 Runtime error 379 ms 26216 KB Execution killed because of forbidden syscall writev (20)
7 Runtime error 279 ms 26216 KB Execution killed because of forbidden syscall writev (20)

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 33 ms 11588 KB Execution killed because of forbidden syscall writev (20)
2 Runtime error 36 ms 11720 KB Execution killed because of forbidden syscall writev (20)
3 Runtime error 109 ms 16052 KB Execution killed because of forbidden syscall writev (20)
4 Runtime error 73 ms 16052 KB Execution killed because of forbidden syscall writev (20)
5 Runtime error 99 ms 16928 KB Execution killed because of forbidden syscall writev (20)
6 Runtime error 186 ms 20888 KB Execution killed because of forbidden syscall writev (20)
7 Runtime error 129 ms 18908 KB Execution killed because of forbidden syscall writev (20)
8 Runtime error 466 ms 30788 KB Execution killed because of forbidden syscall writev (20)
9 Runtime error 926 ms 46400 KB Execution killed because of forbidden syscall writev (20)
10 Runtime error 356 ms 30956 KB Execution killed because of forbidden syscall writev (20)
11 Runtime error 419 ms 32012 KB Execution killed because of forbidden syscall writev (20)
12 Runtime error 809 ms 43364 KB Execution killed because of forbidden syscall writev (20)
13 Runtime error 986 ms 46532 KB Execution killed because of forbidden syscall writev (20)