oj.uz

Submission #171520

# Submission time Handle Problem Language Result Execution time Memory
171520 2019-12-28T21:54:01 Z TadijaSebez Cake (CEOI14_cake) C++11
100 / 100
 1263 ms 19064 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 396 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 7 ms 412 KB Output is correct
5 Correct 19 ms 1016 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 538 ms 1112 KB Output is correct
2 Correct 402 ms 1240 KB Output is correct
3 Correct 458 ms 1232 KB Output is correct
4 Correct 337 ms 1276 KB Output is correct
5 Correct 642 ms 2100 KB Output is correct
6 Correct 577 ms 2024 KB Output is correct
7 Correct 515 ms 2120 KB Output is correct
8 Correct 407 ms 2120 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 7288 KB Output is correct
2 Correct 112 ms 7180 KB Output is correct
3 Correct 106 ms 7136 KB Output is correct
4 Correct 2 ms 400 KB Output is correct
5 Correct 345 ms 15924 KB Output is correct
6 Correct 331 ms 16060 KB Output is correct
7 Correct 193 ms 15812 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 872 KB Output is correct
2 Correct 49 ms 1016 KB Output is correct
3 Correct 127 ms 3808 KB Output is correct
4 Correct 137 ms 3808 KB Output is correct
5 Correct 151 ms 1044 KB Output is correct
6 Correct 234 ms 5064 KB Output is correct
7 Correct 192 ms 1788 KB Output is correct
8 Correct 338 ms 6712 KB Output is correct
9 Correct 1263 ms 18356 KB Output is correct
10 Correct 493 ms 1780 KB Output is correct
11 Correct 640 ms 3292 KB Output is correct
12 Correct 1167 ms 15004 KB Output is correct
13 Correct 915 ms 19064 KB Output is correct