oj.uz

Submission #95208

# Submission time Handle Problem Language Result Execution time Memory
95208 2019-01-28T14:44:55 Z ekrem Cake (CEOI14_cake) C++
0 / 100
 2000 ms 5368 KB 
#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);
		yer[n - b[i] + 1] = 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

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:77:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
cake.cpp:79:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c",&ch);
   ~~~~~^~~~~~~~~~~
cake.cpp:82:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&x);
    ~~~~~^~~~~~~~~
cake.cpp:87: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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1597 ms 1884 KB Output isn't correct
2 Execution timed out 2031 ms 1756 KB Time limit exceeded
3 Incorrect 1981 ms 2008 KB Output isn't correct
4 Execution timed out 2033 ms 1912 KB Time limit exceeded
5 Execution timed out 2065 ms 2168 KB Time limit exceeded
6 Execution timed out 2050 ms 2044 KB Time limit exceeded
7 Execution timed out 2072 ms 2044 KB Time limit exceeded
8 Execution timed out 2062 ms 2168 KB Time limit exceeded

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 3548 KB Output isn't correct
2 Incorrect 44 ms 3316 KB Output isn't correct
3 Incorrect 43 ms 3320 KB Output isn't correct
4 Correct 2 ms 376 KB Output is correct
5 Incorrect 81 ms 5368 KB Output isn't correct
6 Incorrect 79 ms 5368 KB Output isn't correct
7 Incorrect 70 ms 5240 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 888 KB Output isn't correct
2 Incorrect 55 ms 888 KB Output isn't correct
3 Incorrect 639 ms 2232 KB Output isn't correct
4 Incorrect 637 ms 2200 KB Output isn't correct
5 Incorrect 96 ms 1960 KB Output isn't correct
6 Incorrect 1796 ms 3064 KB Output isn't correct
7 Incorrect 404 ms 2448 KB Output isn't correct
8 Execution timed out 2062 ms 2936 KB Time limit exceeded
9 Execution timed out 2037 ms 4988 KB Time limit exceeded
10 Incorrect 309 ms 2888 KB Output isn't correct
11 Incorrect 1855 ms 3448 KB Output isn't correct
12 Execution timed out 2080 ms 4472 KB Time limit exceeded
13 Execution timed out 2069 ms 5112 KB Time limit exceeded