oj.uz

Submission #171504

# Submission time Handle Problem Language Result Execution time Memory
171504 2019-12-28T21:30:03 Z TadijaSebez Cake (CEOI14_cake) C++11
83.3333 / 100
 2000 ms 25788 KB 
#include <bits/stdc++.h>
using namespace std;
const int N=250050;
const int M=2*N;
int ls[M],rs[M],tsz,root,mx[M];
void Set(int &c, int ss, int se, int qi, int val)
{
	if(!c) c=++tsz;
	if(ss==se){ mx[c]=val;return;}
	int mid=ss+se>>1;
	if(qi<=mid) Set(ls[c],ss,mid,qi,val);
	else Set(rs[c],mid+1,se,qi,val);
	mx[c]=max(mx[ls[c]],mx[rs[c]]);
}
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 max(Get(ls[c],ss,mid,qs,qe),Get(rs[c],mid+1,se,qs,qe));
}
set<pair<int,int>> ord;
int d[N];
int main()
{
	int n,q,a;
	scanf("%i %i",&n,&a);
	for(int i=1;i<=n;i++)
	{
		scanf("%i",&d[i]);
		Set(root,1,n,i,d[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=Get(root,1,n,a+1,b);
				int top=a-1,bot=1,mid,ans=a;
				while(top>=bot)
				{
					mid=top+bot>>1;
					if(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=Get(root,1,n,b,a-1);
				int top=n,bot=a+1,mid,ans=a;
				while(top>=bot)
				{
					mid=top+bot>>1;
					if(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]++;
				Set(root,1,n,top.second,top.first);
				bck.push(top);
			}
			int my=1;
			if(ord.size()) my=ord.rbegin()->first+1;
			Set(root,1,n,b,my);
			d[b]=my;
			ord.insert({d[b],b});
			while(bck.size())
			{
				pair<int,int> top=bck.top();
				bck.pop();
				Set(root,1,n,top.second,top.first);
				ord.insert(top);
			}
		}
	}
	return 0;
}

Compilation message

cake.cpp: In function 'void Set(int&, int, int, int, int)':
cake.cpp:10:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
cake.cpp: In function 'int Get(int, int, int, int, int)':
cake.cpp:19:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
cake.cpp: In function 'int main()':
cake.cpp:50:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
      mid=top+bot>>1;
          ~~~^~~~
cake.cpp:62:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
      mid=top+bot>>1;
          ~~~^~~~
cake.cpp:27: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:30:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i",&d[i]);
   ~~~~~^~~~~~~~~~~~
cake.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&q);
  ~~~~~^~~~~~~~~
cake.cpp:38:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("\n%c",&t);
   ~~~~~^~~~~~~~~~~
cake.cpp:42:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%i",&b);
    ~~~~~^~~~~~~~~
cake.cpp:72: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 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 12 ms 504 KB Output is correct
5 Correct 39 ms 1272 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 862 ms 5428 KB Output is correct
2 Correct 523 ms 5624 KB Output is correct
3 Correct 622 ms 5640 KB Output is correct
4 Correct 348 ms 5500 KB Output is correct
5 Correct 1076 ms 6888 KB Output is correct
6 Correct 835 ms 7436 KB Output is correct
7 Correct 720 ms 7176 KB Output is correct
8 Correct 442 ms 7404 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 607 ms 9916 KB Output is correct
2 Correct 416 ms 9888 KB Output is correct
3 Correct 408 ms 9720 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 733 ms 22260 KB Output is correct
6 Correct 883 ms 22188 KB Output is correct
7 Correct 634 ms 21928 KB Output is correct

Subtask #4
33.333333 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 1144 KB Output is correct
2 Correct 106 ms 1244 KB Output is correct
3 Correct 304 ms 5356 KB Output is correct
4 Correct 331 ms 5216 KB Output is correct
5 Correct 292 ms 1912 KB Output is correct
6 Correct 621 ms 7544 KB Output is correct
7 Correct 396 ms 3484 KB Output is correct
8 Correct 479 ms 10396 KB Output is correct
9 Execution timed out 2043 ms 25188 KB Time limit exceeded
10 Correct 968 ms 5336 KB Output is correct
11 Correct 1467 ms 7556 KB Output is correct
12 Execution timed out 2066 ms 21320 KB Time limit exceeded
13 Execution timed out 2065 ms 25788 KB Time limit exceeded