oj.uz

Submission #171580

# Submission time Handle Problem Language Result Execution time Memory
171580 2019-12-29T09:39:57 Z MvC Cake (CEOI14_cake) C++11
100 / 100
 1485 ms 18556 KB 
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=3e5+50;
const int mod=1e9+7;
using namespace std;
int n,i,j,e,st,ed,p,sg[4*nmax],q,mx,a[nmax],vl;
char c;
vector<pair<int,int> >vc;
set<pair<int,int> >s;
set<pair<int,int> >::iterator it;
void upd(int x,int l,int r,int p,int v)
{
	if(l==r)
	{
		sg[x]=v;
		return;
	}
	int mid=(l+r)/2;
	if(p<=mid)upd(2*x,l,mid,p,v);
	else upd(2*x+1,mid+1,r,p,v);
	sg[x]=max(sg[2*x],sg[2*x+1]);
}
int qry(int x,int l,int r,int tl,int tr)
{
	if(tl>r || l>tr)return 0;
	if(tl<=l && r<=tr)return sg[x];
	int mid=(l+r)/2;
	return max(qry(2*x,l,mid,tl,tr),qry(2*x+1,mid+1,r,tl,tr));
}
int lft(int x,int l,int r,int tl,int tr,int v)
{
	if(l>r || tl>tr)return -1;
	if(sg[x]<v)return -1;
	if(l==r)return l;
	int mid=(l+r)/2,rt=-1;
	if(tl<=l && r<=tr)
	{
		if(sg[2*x+1]>v)return lft(2*x+1,mid+1,r,tl,tr,v);
		if(sg[2*x]>v)return lft(2*x,l,mid,tl,tr,v);
		return -1;
	}
	if(tr>mid)rt=lft(2*x+1,mid+1,r,tl,tr,v);
	if(tl<=mid && rt==-1)rt=lft(2*x,l,mid,tl,tr,v);
	return rt;
}
int rgt(int x,int l,int r,int tl,int tr,int v)
{
	if(l>r || tl>tr)return -1;
	if(sg[x]<v)return -1;
	if(l==r)return l;
	int mid=(l+r)/2,rt=-1;
	if(tl<=l && r<=tr)
	{
		if(sg[2*x]>v)return rgt(2*x,l,mid,tl,tr,v);
		if(sg[2*x+1]>v)return rgt(2*x+1,mid+1,r,tl,tr,v);
		return -1;
	}
	if(tl<=mid)rt=rgt(2*x,l,mid,tl,tr,v);
	if(tr>mid && rt==-1)rt=rgt(2*x+1,mid+1,r,tl,tr,v);
	return rt;
}
int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>n>>st;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
		s.in(mkp(a[i],i));
		upd(1,1,n,i,a[i]);
	}
	cin>>q;
	while(q--)
	{
		cin>>c;
		if(c=='E')
		{
			cin>>i>>e;
			vc.clear();
			it=s.end(),it--;
			for(j=1;j<e;j++)vc.pb(*it),it--;
			vc.pb(mkp(a[i],i));
			reverse(vc.begin(),vc.end());
			it=s.end(),it--;
			vl=(it->fr)+1;
			for(j=0;j<e;j++)s.er(s.fd(vc[j]));
			vc[0].fr=vl;
			for(j=1;j<e;j++)vc[j].fr=vc[j-1].fr+1;
			for(j=0;j<e;j++)
			{
				s.in(vc[j]);
				upd(1,1,n,vc[j].sc,vc[j].fr);
				a[vc[j].sc]=vc[j].fr;
			}
			//for(j=1;j<=n;j++)cout<<a[j]<<" ";
			//cout<<endl;
		}
		else
		{
			cin>>ed;
			if(ed==st)cout<<0<<'\n';
			else if(ed<st)
			{
				mx=qry(1,1,n,ed,st-1);
				p=rgt(1,1,n,st+1,n,mx);
				if(p==-1)p=n+1;
				cout<<p-ed-1<<'\n';
			}
			else
			{
				mx=qry(1,1,n,st+1,ed);
				p=lft(1,1,n,1,st-1,mx);
				if(p==-1)p=0;
				cout<<ed-p-1<<'\n';
			}
		}
	}
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 8 ms 504 KB Output is correct
5 Correct 20 ms 1016 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 615 ms 1152 KB Output is correct
2 Correct 312 ms 1400 KB Output is correct
3 Correct 420 ms 1352 KB Output is correct
4 Correct 193 ms 1272 KB Output is correct
5 Correct 757 ms 2156 KB Output is correct
6 Correct 571 ms 2040 KB Output is correct
7 Correct 502 ms 2168 KB Output is correct
8 Correct 256 ms 2172 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 7288 KB Output is correct
2 Correct 110 ms 7140 KB Output is correct
3 Correct 103 ms 7148 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 376 ms 15996 KB Output is correct
6 Correct 395 ms 16132 KB Output is correct
7 Correct 183 ms 15864 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 888 KB Output is correct
2 Correct 50 ms 1016 KB Output is correct
3 Correct 133 ms 3804 KB Output is correct
4 Correct 188 ms 3960 KB Output is correct
5 Correct 174 ms 1220 KB Output is correct
6 Correct 228 ms 4828 KB Output is correct
7 Correct 181 ms 1784 KB Output is correct
8 Correct 320 ms 6776 KB Output is correct
9 Correct 1485 ms 18556 KB Output is correct
10 Correct 585 ms 2148 KB Output is correct
11 Correct 802 ms 3232 KB Output is correct
12 Correct 1377 ms 15028 KB Output is correct
13 Correct 1033 ms 18040 KB Output is correct