oj.uz

Submission #171506

# Submission time Handle Problem Language Result Execution time Memory
171506 2019-12-28T21:33:02 Z TadijaSebez Cake (CEOI14_cake) C++11
83.3333 / 100
 2000 ms 17000 KB 
#include <bits/stdc++.h>
using namespace std;
#define ls c<<1
#define rs c<<1|1
const int N=250050;
const int M=4*N;
int root=1,mx[M];
void Set(int c, int ss, int se, int qi, int val)
{
	if(ss==se){ mx[c]=val;return;}
	int mid=ss+se>>1;
	if(qi<=mid) Set(ls,ss,mid,qi,val);
	else Set(rs,mid+1,se,qi,val);
	mx[c]=max(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 max(Get(ls,ss,mid,qs,qe),Get(rs,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:11: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:20:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
cake.cpp: In function 'int main()':
cake.cpp:51:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
      mid=top+bot>>1;
          ~~~^~~~
cake.cpp:63:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
      mid=top+bot>>1;
          ~~~^~~~
cake.cpp:28: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:31:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i",&d[i]);
   ~~~~~^~~~~~~~~~~~
cake.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&q);
  ~~~~~^~~~~~~~~
cake.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("\n%c",&t);
   ~~~~~^~~~~~~~~~~
cake.cpp:43:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%i",&b);
    ~~~~~^~~~~~~~~
cake.cpp:73: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 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 11 ms 376 KB Output is correct
5 Correct 34 ms 1016 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 768 ms 968 KB Output is correct
2 Correct 482 ms 888 KB Output is correct
3 Correct 562 ms 1048 KB Output is correct
4 Correct 340 ms 1016 KB Output is correct
5 Correct 907 ms 2012 KB Output is correct
6 Correct 796 ms 1916 KB Output is correct
7 Correct 691 ms 1912 KB Output is correct
8 Correct 446 ms 1784 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 643 ms 7296 KB Output is correct
2 Correct 425 ms 7032 KB Output is correct
3 Correct 440 ms 7032 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 728 ms 16164 KB Output is correct
6 Correct 888 ms 15864 KB Output is correct
7 Correct 672 ms 15508 KB Output is correct

Subtask #4
33.333333 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 668 KB Output is correct
2 Correct 112 ms 760 KB Output is correct
3 Correct 307 ms 3636 KB Output is correct
4 Correct 296 ms 3848 KB Output is correct
5 Correct 298 ms 888 KB Output is correct
6 Correct 590 ms 4828 KB Output is correct
7 Correct 389 ms 1528 KB Output is correct
8 Correct 422 ms 6776 KB Output is correct
9 Execution timed out 2079 ms 17000 KB Time limit exceeded
10 Correct 991 ms 1656 KB Output is correct
11 Correct 1438 ms 3184 KB Output is correct
12 Execution timed out 2068 ms 14528 KB Time limit exceeded
13 Execution timed out 2056 ms 16668 KB Time limit exceeded