oj.uz

Submission #30815

# Submission time Handle Problem Language Result Execution time Memory
30815 2017-07-27T03:40:40 Z zscoder Cake (CEOI14_cake) C++14
0 / 100
 923 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 = 0; i < q; 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<<i<<' '<<a[i]<<'\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);
		}
		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';
			}
		}
	}
}

Subtask #1
0 / 15.0

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

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 793 ms 46928 KB Output isn't correct
2 Incorrect 773 ms 47060 KB Output isn't correct
3 Incorrect 739 ms 47060 KB Output isn't correct
4 Incorrect 799 ms 47060 KB Output isn't correct
5 Incorrect 863 ms 47984 KB Output isn't correct
6 Incorrect 829 ms 47984 KB Output isn't correct
7 Incorrect 879 ms 47984 KB Output isn't correct
8 Incorrect 829 ms 47984 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 129 ms 16844 KB Execution killed because of forbidden syscall writev (20)
2 Runtime error 89 ms 16844 KB Execution killed because of forbidden syscall writev (20)
3 Runtime error 93 ms 16844 KB Execution killed because of forbidden syscall writev (20)
4 Incorrect 0 ms 9068 KB Output isn't correct
5 Runtime error 396 ms 26216 KB Execution killed because of forbidden syscall writev (20)
6 Runtime error 419 ms 26216 KB Execution killed because of forbidden syscall writev (20)
7 Runtime error 299 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 26 ms 11588 KB Execution killed because of forbidden syscall writev (20)
2 Runtime error 23 ms 11720 KB Execution killed because of forbidden syscall writev (20)
3 Runtime error 129 ms 16052 KB Execution killed because of forbidden syscall writev (20)
4 Runtime error 96 ms 16052 KB Execution killed because of forbidden syscall writev (20)
5 Runtime error 89 ms 16928 KB Execution killed because of forbidden syscall writev (20)
6 Runtime error 209 ms 20888 KB Execution killed because of forbidden syscall writev (20)
7 Runtime error 133 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 826 ms 46400 KB Execution killed because of forbidden syscall writev (20)
10 Runtime error 373 ms 30956 KB Execution killed because of forbidden syscall writev (20)
11 Runtime error 433 ms 32012 KB Execution killed because of forbidden syscall writev (20)
12 Runtime error 769 ms 43364 KB Execution killed because of forbidden syscall writev (20)
13 Runtime error 923 ms 46532 KB Execution killed because of forbidden syscall writev (20)