oj.uz

Submission #171512

# Submission time Handle Problem Language Result Execution time Memory
171512 2019-12-28T21:41:02 Z TadijaSebez Cake (CEOI14_cake) C++11
83.3333 / 100
 2000 ms 17736 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];
int d[N];
int cmb(int i, int j){ return d[i]>d[j]?i:j;}
void Set(int c, int ss, int se, int qi)
{
	if(ss==se){ mx[c]=qi;return;}
	int mid=ss+se>>1;
	if(qi<=mid) Set(ls,ss,mid,qi);
	else Set(rs,mid+1,se,qi);
	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));
}
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]);
		Set(root,1,n,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[Get(root,1,n,a+1,b)];
				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[Get(root,1,n,b,a-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;
			Set(root,1,n,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 function 'void Set(int, int, int, int)':
cake.cpp:13: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:22:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
cake.cpp: In function 'int main()':
cake.cpp:52:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
      mid=top+bot>>1;
          ~~~^~~~
cake.cpp:64:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
      mid=top+bot>>1;
          ~~~^~~~
cake.cpp:29: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:32:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i",&d[i]);
   ~~~~~^~~~~~~~~~~~
cake.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&q);
  ~~~~~^~~~~~~~~
cake.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("\n%c",&t);
   ~~~~~^~~~~~~~~~~
cake.cpp:44:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%i",&b);
    ~~~~~^~~~~~~~~
cake.cpp:74: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 400 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 9 ms 376 KB Output is correct
5 Correct 29 ms 1152 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 548 ms 1128 KB Output is correct
2 Correct 417 ms 1228 KB Output is correct
3 Correct 471 ms 1272 KB Output is correct
4 Correct 352 ms 1224 KB Output is correct
5 Correct 655 ms 2168 KB Output is correct
6 Correct 581 ms 2040 KB Output is correct
7 Correct 523 ms 2124 KB Output is correct
8 Correct 426 ms 2116 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 655 ms 7504 KB Output is correct
2 Correct 452 ms 7148 KB Output is correct
3 Correct 466 ms 7028 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 797 ms 16116 KB Output is correct
6 Correct 914 ms 16136 KB Output is correct
7 Correct 695 ms 15800 KB Output is correct

Subtask #4
33.333333 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 860 KB Output is correct
2 Correct 110 ms 1104 KB Output is correct
3 Correct 300 ms 3960 KB Output is correct
4 Correct 254 ms 3832 KB Output is correct
5 Correct 242 ms 1056 KB Output is correct
6 Correct 571 ms 4952 KB Output is correct
7 Correct 370 ms 1804 KB Output is correct
8 Correct 361 ms 6832 KB Output is correct
9 Execution timed out 2041 ms 17736 KB Time limit exceeded
10 Correct 795 ms 1740 KB Output is correct
11 Correct 1171 ms 3200 KB Output is correct
12 Execution timed out 2065 ms 15312 KB Time limit exceeded
13 Execution timed out 2062 ms 17440 KB Time limit exceeded