Submission #95210

#	Time	Username	Problem	Language	Result	Execution time	Memory
95210		ekrem	Cake (CEOI14_cake)	C++98	0 / 100	2073 ms	4060 KiB

cake

#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define N 1000005
using namespace std;

int n, m, c, q, l, r, mx, a[N], b[N], u[N], yer[N];
pair < int , int > amk;
char ch;

void yap(int l, int r, int x, int art){
	if(art >= 1)
		for(int i = l; i <= r; i++, x++)
			a[i] = x;
	else
		for(int i = l; i >= r; i--, x++)
			a[i] = x;
}

void duzenle(){
	l = 1;
	r = n;
	for(int i = 1; i <= mx; i++){
		if(yer[i] < l or yer[i] > r)
			continue;
		if(c < yer[i]){
			yap(yer[i], r, yer[i] - l + 1, 1);
			r = yer[i] - 1;
		}
		else{
			yap(yer[i], l, r - yer[i] + 1, -1);
			l = yer[i] + 1;
		}
	}
}

int main() {
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	scanf("%d %d",&n ,&c);
	for(int i = 1; i <= n; i++)
		scanf("%d",b + i);
	mx = min(10, n - 1);

	u[c] = 1;
	for(int i = 1; i <= mx; i++){
		amk = mp(0, 0);
		for(int j = 1; j <= n; j++)
			if(!u[j])
				amk = max(amk, mp(b[j], j));
		yer[i] = amk.nd;
		u[amk.nd] = 1;
	}
	// for(int i = 1; i <= mx; i++)
	// 	cout << yer[i] << endl;

	l = c - 1;
	r = c + 1;
	a[c] = ++m;
	while(l >= 1 and r <= n){
		if(b[l] < b[r])
			a[l--] = ++m;
		else
			a[r++] = ++m;
	}
	while(l >= 1)
		a[l--] = ++m;
	while(r <= n)
		a[r++] = ++m;
	// for(int i = 1; i <= n; i++)
	// 	cout << a[i] << " ";
	// cout << endl;
	scanf("%d",&q);
	while(q--){
		scanf(" %c",&ch);
		if(ch == 'F'){
			int x;
			scanf("%d",&x);
			printf("%d\n", a[x] - 1);
			continue;
		}
		int x, y;
		scanf("%d %d",&x ,&y);
		if(x == c)
			continue;
		for(int i = mx; i >= y + 1; i--)
			yer[i] = yer[i - 1];

		yer[y] = x;

		// for(int i = 1; i <= mx; i++)
		// 	cout << yer[i] << " ";
		// cout << endl;

		// for(int i = 1; i <= n; i++)
		// 	cout << a[i] << " ";
		// cout << endl;

		duzenle();
		// for(int i = 1; i <= n; i++)
		// 	cout << a[i] << " ";
		// cout << endl;
	}
	return 0;
}

Compilation message (stderr)

cake.cpp: In function 'int main()':
cake.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n ,&c);
  ~~~~~^~~~~~~~~~~~~~~~
cake.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",b + i);
   ~~~~~^~~~~~~~~~~~
cake.cpp:75:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
cake.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c",&ch);
   ~~~~~^~~~~~~~~~~
cake.cpp:80:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&x);
    ~~~~~^~~~~~~~~
cake.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x ,&y);
   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 50