oj.uz

답안 #95205

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
95205 2019-01-28T14:37:34 Z ekrem 케이크 (CEOI14_cake) C++
0 / 100
 2000 ms 6392 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);
		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

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

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1610 ms 4908 KB Output isn't correct
2 Execution timed out 2041 ms 5004 KB Time limit exceeded
3 Incorrect 1987 ms 4884 KB Output isn't correct
4 Execution timed out 2052 ms 4924 KB Time limit exceeded
5 Execution timed out 2066 ms 3436 KB Time limit exceeded
6 Execution timed out 2065 ms 3080 KB Time limit exceeded
7 Execution timed out 2069 ms 3336 KB Time limit exceeded
8 Execution timed out 2069 ms 3148 KB Time limit exceeded

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 49 ms 3448 KB Output isn't correct
2 Incorrect 45 ms 3308 KB Output isn't correct
3 Incorrect 45 ms 3320 KB Output isn't correct
4 Incorrect 2 ms 376 KB Output isn't correct
5 Incorrect 82 ms 6392 KB Output isn't correct
6 Incorrect 78 ms 6392 KB Output isn't correct
7 Incorrect 68 ms 6248 KB Output isn't correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 40 ms 888 KB Output isn't correct
2 Incorrect 56 ms 944 KB Output isn't correct
3 Incorrect 628 ms 2244 KB Output isn't correct
4 Incorrect 632 ms 2044 KB Output isn't correct
5 Incorrect 94 ms 1784 KB Output isn't correct
6 Incorrect 1800 ms 3388 KB Output isn't correct
7 Incorrect 399 ms 2680 KB Output isn't correct
8 Execution timed out 2061 ms 3168 KB Time limit exceeded
9 Execution timed out 2054 ms 5880 KB Time limit exceeded
10 Incorrect 312 ms 5240 KB Output isn't correct
11 Incorrect 1876 ms 6376 KB Output isn't correct
12 Execution timed out 2064 ms 5124 KB Time limit exceeded
13 Execution timed out 2063 ms 6156 KB Time limit exceeded