oj.uz

Submission #95210

# Submission time Handle Problem Language Result Execution time Memory
95210 2019-01-28T14:47:13 Z ekrem Cake (CEOI14_cake) C++
0 / 100
 2000 ms 4060 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);
	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: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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 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 1646 ms 1468 KB Output isn't correct
2 Execution timed out 2053 ms 1588 KB Time limit exceeded
3 Incorrect 1991 ms 1528 KB Output isn't correct
4 Execution timed out 2054 ms 1400 KB Time limit exceeded
5 Execution timed out 2047 ms 1748 KB Time limit exceeded
6 Execution timed out 2058 ms 1592 KB Time limit exceeded
7 Execution timed out 2045 ms 1540 KB Time limit exceeded
8 Execution timed out 2073 ms 1552 KB Time limit exceeded

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 2340 KB Output isn't correct
2 Incorrect 44 ms 2296 KB Output isn't correct
3 Incorrect 45 ms 2172 KB Output isn't correct
4 Correct 2 ms 376 KB Output is correct
5 Incorrect 75 ms 4028 KB Output isn't correct
6 Incorrect 73 ms 3960 KB Output isn't correct
7 Incorrect 67 ms 4060 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 630 ms 1884 KB Output isn't correct
4 Incorrect 649 ms 1668 KB Output isn't correct
5 Incorrect 93 ms 1404 KB Output isn't correct
6 Incorrect 1785 ms 2424 KB Output isn't correct
7 Incorrect 396 ms 1912 KB Output isn't correct
8 Execution timed out 2065 ms 1912 KB Time limit exceeded
9 Execution timed out 2033 ms 3820 KB Time limit exceeded
10 Incorrect 307 ms 2536 KB Output isn't correct
11 Incorrect 1888 ms 3108 KB Output isn't correct
12 Execution timed out 2067 ms 3320 KB Time limit exceeded
13 Execution timed out 2065 ms 3576 KB Time limit exceeded