oj.uz

답안 #171509

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
171509 2019-12-28T21:37:11 Z TadijaSebez 케이크 (CEOI14_cake) C++11
0 / 100
 2000 ms 18148 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;
			Set(root,1,n,b);
			d[b]=my;
			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
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 552 ms 1176 KB Output isn't correct
2 Incorrect 417 ms 1240 KB Output isn't correct
3 Incorrect 473 ms 1232 KB Output isn't correct
4 Correct 348 ms 1236 KB Output is correct
5 Incorrect 670 ms 2100 KB Output isn't correct
6 Incorrect 587 ms 2128 KB Output isn't correct
7 Incorrect 532 ms 2120 KB Output isn't correct
8 Correct 422 ms 2124 KB Output is correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 590 ms 7224 KB Output isn't correct
2 Incorrect 394 ms 7176 KB Output isn't correct
3 Incorrect 421 ms 7148 KB Output isn't correct
4 Correct 2 ms 376 KB Output is correct
5 Incorrect 709 ms 15984 KB Output isn't correct
6 Incorrect 870 ms 15960 KB Output isn't correct
7 Correct 629 ms 15788 KB Output is correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 97 ms 892 KB Output isn't correct
2 Incorrect 99 ms 940 KB Output isn't correct
3 Incorrect 274 ms 3844 KB Output isn't correct
4 Incorrect 238 ms 3872 KB Output isn't correct
5 Incorrect 224 ms 988 KB Output isn't correct
6 Incorrect 518 ms 4852 KB Output isn't correct
7 Incorrect 345 ms 1668 KB Output isn't correct
8 Incorrect 370 ms 6716 KB Output isn't correct
9 Execution timed out 2032 ms 18148 KB Time limit exceeded
10 Incorrect 739 ms 1924 KB Output isn't correct
11 Incorrect 1081 ms 3304 KB Output isn't correct
12 Execution timed out 2003 ms 15736 KB Time limit exceeded
13 Execution timed out 2033 ms 17936 KB Time limit exceeded