oj.uz

답안 #454956

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
454956 2021-08-05T10:50:18 Z kingfran1907 케이크 (CEOI14_cake) C++14
0 / 100
 697 ms 16484 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 = 18;
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, llint 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--;
			
			vector< int > v;
			llint val = s.begin()->first; val *= -1;
			for (int i = 0; i < pos - 1; i++) {
				int tr = s.begin()->second;
				s.erase(s.begin());
				niz[tr] = val + pos - i;
				v.push_back(tr);
			}
			
			s.erase(make_pair(-niz[ind], ind));
			niz[ind] = val + 1;
			s.insert(make_pair(-niz[ind], ind));
			update(ind, niz[ind]);
			
			for (int tren : v) {
				update(tren, niz[tren]);
				s.insert(make_pair(-niz[tren], tren));
			}
			while (s.size() > 11) s.erase(--s.end());
		} 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: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:103:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |    scanf("%d", &x); x--;
      |    ~~~~~^~~~~~~~~~

Subtask #1
0 / 15.0

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

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 491 ms 12532 KB Output is correct
2 Incorrect 341 ms 12288 KB Output isn't correct
3 Correct 351 ms 12540 KB Output is correct
4 Correct 249 ms 8564 KB Output is correct
5 Correct 504 ms 12788 KB Output is correct
6 Incorrect 481 ms 13168 KB Output isn't correct
7 Correct 513 ms 13044 KB Output is correct
8 Correct 243 ms 8688 KB Output is correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 106 ms 9800 KB Output isn't correct
2 Incorrect 85 ms 9668 KB Output isn't correct
3 Incorrect 75 ms 9648 KB Output isn't correct
4 Incorrect 5 ms 8396 KB Output isn't correct
5 Correct 127 ms 11076 KB Output is correct
6 Incorrect 135 ms 11056 KB Output isn't correct
7 Incorrect 112 ms 10928 KB Output isn't correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 81 ms 8568 KB Output isn't correct
2 Incorrect 41 ms 8672 KB Output isn't correct
3 Incorrect 76 ms 9388 KB Output isn't correct
4 Incorrect 97 ms 9284 KB Output isn't correct
5 Incorrect 147 ms 9576 KB Output isn't correct
6 Incorrect 135 ms 10444 KB Output isn't correct
7 Incorrect 143 ms 10224 KB Output isn't correct
8 Correct 214 ms 10820 KB Output is correct
9 Incorrect 697 ms 16484 KB Output isn't correct
10 Incorrect 516 ms 12924 KB Output isn't correct
11 Incorrect 567 ms 13900 KB Output isn't correct
12 Correct 680 ms 16048 KB Output is correct
13 Correct 608 ms 16452 KB Output is correct