Submission #171520

#	Time	Username	Problem	Language	Result	Execution time	Memory
171520		TadijaSebez	Cake (CEOI14_cake)	C++11	100 / 100	1263 ms	19064 KiB

cake

#include <bits/stdc++.h>
using namespace std;
#define ls c<<1
#define rs c<<1|1
#define root 1
const int N=250050;
const int M=4*N;
int d[N];
struct SegmentTree
{
	int mx[M];
	int cmb(int i, int j){ return d[i]>d[j]?i:j;}
	void Set(int c, int ss, int se, int qi, int id)
	{
		if(ss==se){ mx[c]=id;return;}
		int mid=ss+se>>1;
		if(qi<=mid) Set(ls,ss,mid,qi,id);
		else Set(rs,mid+1,se,qi,id);
		mx[c]=cmb(mx[ls],mx[rs]);
	}
	int Get(int c, int ss, int se, int qs, int qe)
	{
		if(qs>qe || qs>se || ss>qe) return 0;
		if(qs<=ss && qe>=se) return mx[c];
		int mid=ss+se>>1;
		return cmb(Get(ls,ss,mid,qs,qe),Get(rs,mid+1,se,qs,qe));
	}
	int Search(int c, int ss, int se, int val)
	{
		if(ss==se) return val<=d[mx[c]]?ss:ss+1;
		int mid=ss+se>>1;
		if(d[mx[ls]]<val) return Search(rs,mid+1,se,val);
		else return Search(ls,ss,mid,val);
	}
} L,R;
set<pair<int,int>> ord;
int main()
{
	int n,q,a;
	scanf("%i %i",&n,&a);
	for(int i=1;i<=n;i++)
	{
		scanf("%i",&d[i]);
		if(i<a) L.Set(root,1,a-1,a-i,i);
		if(i>a) R.Set(root,1,n-a,i-a,i);
		ord.insert({d[i],i});
	}
	scanf("%i",&q);
	while(q--)
	{
		char t;
		scanf("\n%c",&t);
		if(t=='F')
		{
			int b;
			scanf("%i",&b);
			if(b==a) printf("0\n");
			else if(b>a)
			{
				int val=d[R.Get(root,1,n-a,1,b-a)];
				printf("%i\n",b-a+L.Search(root,1,a-1,val)-1);
				/*int top=a-1,bot=1,mid,ans=a;
				while(top>=bot)
				{
					mid=top+bot>>1;
					if(d[Get(root,1,n,mid,a-1)]<val) top=mid-1,ans=mid;
					else bot=mid+1;
				}
				printf("%i\n",b-ans);*/
			}
			else
			{
				int val=d[L.Get(root,1,a-1,1,a-b)];
				printf("%i\n",a-b+R.Search(root,1,n-a,val)-1);
				/*int top=n,bot=a+1,mid,ans=a;
				while(top>=bot)
				{
					mid=top+bot>>1;
					if(d[Get(root,1,n,a+1,mid)]<val) bot=mid+1,ans=mid;
					else top=mid-1;
				}
				printf("%i\n",ans-b);*/
			}
		}
		else
		{
			int b,e;
			scanf("%i %i",&b,&e);
			stack<pair<int,int>> bck;
			ord.erase({d[b],b});
			while(--e)
			{
				pair<int,int> top=*ord.rbegin();
				ord.erase(--ord.end());
				top.first++;
				d[top.second]++;
				bck.push(top);
			}
			int my=1;
			if(ord.size()) my=ord.rbegin()->first+1;
			d[b]=my;
			if(b<a) L.Set(root,1,a-1,a-b,b);
			if(b>a) R.Set(root,1,n-a,b-a,b);
			ord.insert({d[b],b});
			while(bck.size())
			{
				pair<int,int> top=bck.top();
				bck.pop();
				ord.insert(top);
			}
		}
	}
	return 0;
}

Compilation message (stderr)

cake.cpp: In member function 'void SegmentTree::Set(int, int, int, int, int)':
cake.cpp:16:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=ss+se>>1;
           ~~^~~
cake.cpp: In member function 'int SegmentTree::Get(int, int, int, int, int)':
cake.cpp:25:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=ss+se>>1;
           ~~^~~
cake.cpp: In member function 'int SegmentTree::Search(int, int, int, int)':
cake.cpp:31:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=ss+se>>1;
           ~~^~~
cake.cpp: In function 'int main()':
cake.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&a);
  ~~~~~^~~~~~~~~~~~~~~
cake.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i",&d[i]);
   ~~~~~^~~~~~~~~~~~
cake.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&q);
  ~~~~~^~~~~~~~~
cake.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("\n%c",&t);
   ~~~~~^~~~~~~~~~~
cake.cpp:56:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%i",&b);
    ~~~~~^~~~~~~~~
cake.cpp:88:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%i %i",&b,&e);
    ~~~~~^~~~~~~~~~~~~~~

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