답안 #454922

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
454922 2021-08-05T10:36:29 Z kingfran1907 케이크 (CEOI14_cake) C++14
0 / 100
2000 ms 21884 KB
#include <bits/stdc++.h>
#define X first
#define Y second
 
using namespace std;
typedef long long llint;
 
const int maxn = 3e5+10;
const int base = 31337;
const int mod = 1e9+7;
const llint inf = (1LL << 55);
const int logo = 19;
const int off = 1 << logo;
const int treesiz = off << 1;

struct tournament {
	llint tour[treesiz];
	
	tournament() {
		for (int i = 0; i < treesiz; i++) 
			tour[i] = inf;
	}
	
	void update(int x, llint val) {
		x += off;
		tour[x] = val;
		
		x /= 2;
		while (x > 0) tour[x] = max(tour[x * 2], tour[x * 2 + 1]), x /= 2;
	}
	
	llint query(int a, int b, int l, int r, int node) {
		if (l > b || r < a) return -inf;
		if (l >= a && r <= b) return tour[node];
		
		int mid = (l + r) / 2;
		return max(query(a, b, l, mid, node * 2), query(a, b, mid + 1, r, node * 2 + 1));
	}
	
	int fin(int l, int r, int node, llint val) {
		if (l == r) return l;
		
		int mid = (l + r) / 2;
		//printf("looking: (%d %d) %d (%d) --> %lld %lld\n", l, r, node, val, tour[node * 2], tour[node * 2 + 1]);
		if (tour[node * 2] < val) return fin(mid + 1, r, node * 2 + 1, val);
		return fin(l, mid, node * 2, val);
	}
} lef, rig;

int n, q;
int a;
llint niz[maxn];

void update(int x, int val) {
	if (x <= a) lef.update(a - x, val);
	else rig.update(x - a - 1, val);
}

int main() {
	scanf("%d%d", &n, &a); a--;
	for (int i = 0; i < n; i++) {
		scanf("%lld", niz+i);
	}
	
	for (int i = 0; i < n; i++) update(i, niz[i]);
	
	set< pair<llint, int> > s;
	for (int i = 0; i < n; i++) {
		s.insert(make_pair(-niz[i], i));
		while (s.size() > 11) s.erase(--s.end());
	}
	
	scanf("%d", &q);
	while (q--) {
		char type;
		scanf(" %c", &type);
		
		if (type == 'E') {
			int ind, pos;
			scanf("%d%d", &ind, &pos); ind--;
			
			int cnt = pos - 1;
			auto iter = s.begin();
			while (cnt-- > 0) iter++;
			
			llint val = -(iter->first) + 1;
			
			vector< int > v;
			for (iter = s.begin(); iter != s.end(); iter++) v.push_back(iter->second);
			s.clear();
			
			llint cp = val;
			for (int i = pos - 2; i >= 0; i--) {
				int tr = v[i];
				niz[tr] = ++cp;
				update(tr, niz[tr]);
			}
			for (int i = 0; i < v.size(); i++) s.insert(make_pair(-niz[v[i]], v[i]));
			
			s.erase(make_pair(-niz[ind], ind));
			niz[ind] = val;
			s.insert(make_pair(-niz[ind], ind));
			update(ind, niz[ind]);
		} else {
			int x;
			scanf("%d", &x); x--;
			
			if (x == a) printf("0\n");
			else if (x <= a) {
				int sol = a - x;
				int maxi = lef.query(0, a - x, 0, off - 1, 1);
				int kol = rig.fin(0, off - 1, 1, maxi);
				
				printf("%d\n", sol + kol);
			} else {
				int sol = x - a - 1;
				llint maxi = rig.query(0, x - a - 1, 0, off - 1, 1);
				int kol = lef.fin(0, off - 1, 1, maxi);
				
				printf("%d\n", sol + kol);
			}
		}
	}
	return 0;
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:98:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |    for (int i = 0; i < v.size(); i++) s.insert(make_pair(-niz[v[i]], v[i]));
      |                    ~~^~~~~~~~~~
cake.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |  scanf("%d%d", &n, &a); a--;
      |  ~~~~~^~~~~~~~~~~~~~~~
cake.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |   scanf("%lld", niz+i);
      |   ~~~~~^~~~~~~~~~~~~~~
cake.cpp:73:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
cake.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |   scanf(" %c", &type);
      |   ~~~~~^~~~~~~~~~~~~~
cake.cpp:80:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |    scanf("%d%d", &ind, &pos); ind--;
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~
cake.cpp:106:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |    scanf("%d", &x); x--;
      |    ~~~~~^~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 16716 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2085 ms 17356 KB Time limit exceeded
2 Execution timed out 2091 ms 17456 KB Time limit exceeded
3 Execution timed out 2087 ms 17240 KB Time limit exceeded
4 Correct 694 ms 21188 KB Output is correct
5 Execution timed out 2071 ms 17552 KB Time limit exceeded
6 Execution timed out 2082 ms 17616 KB Time limit exceeded
7 Execution timed out 2085 ms 17568 KB Time limit exceeded
8 Correct 674 ms 21884 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 93 ms 19412 KB Output isn't correct
2 Incorrect 84 ms 19336 KB Output isn't correct
3 Incorrect 76 ms 19268 KB Output isn't correct
4 Incorrect 9 ms 16716 KB Output isn't correct
5 Correct 134 ms 21700 KB Output is correct
6 Incorrect 126 ms 21840 KB Output isn't correct
7 Incorrect 109 ms 21576 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2083 ms 17436 KB Time limit exceeded
2 Execution timed out 2073 ms 17512 KB Time limit exceeded
3 Execution timed out 2060 ms 18240 KB Time limit exceeded
4 Execution timed out 2068 ms 18312 KB Time limit exceeded
5 Execution timed out 2065 ms 17344 KB Time limit exceeded
6 Execution timed out 2076 ms 18236 KB Time limit exceeded
7 Execution timed out 2062 ms 17648 KB Time limit exceeded
8 Execution timed out 2089 ms 18516 KB Time limit exceeded
9 Execution timed out 2063 ms 20984 KB Time limit exceeded
10 Execution timed out 2056 ms 17260 KB Time limit exceeded
11 Execution timed out 2044 ms 17728 KB Time limit exceeded
12 Execution timed out 2059 ms 20140 KB Time limit exceeded
13 Execution timed out 2099 ms 20944 KB Time limit exceeded