oj.uz

Submission #455002

# Submission time Handle Problem Language Result Execution time Memory
455002 2021-08-05T11:24:14 Z kingfran1907 Cake (CEOI14_cake) C++14
100 / 100
 635 ms 17800 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 - 1, val);
	else if (x > a) 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() > 10) s.erase(*s.rbegin());
	}
	
	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() > 10) s.erase(*s.rbegin());
			
			//for (int i = 0; i < n; i++) printf("%d ", niz[i]); printf("\n");
		} 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 - 1, 0, off - 1, 1);
				int kol = rig.fin(0, off - 1, 1, maxi);
				
				//printf("debug %d %d\n", sol, kol);
				printf("%d\n", sol + kol);
			} else {
				int sol = x - a;
				llint maxi = rig.query(0, x - a - 1, 0, off - 1, 1);
				int kol = lef.fin(0, off - 1, 1, maxi);
				
				//printf("debug %d %d\n", sol, kol);
				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:105:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |    scanf("%d", &x); x--;
      |    ~~~~~^~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8396 KB Output is correct
2 Correct 5 ms 8396 KB Output is correct
3 Correct 5 ms 8396 KB Output is correct
4 Correct 10 ms 8500 KB Output is correct
5 Correct 16 ms 8716 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 471 ms 13016 KB Output is correct
2 Correct 278 ms 12896 KB Output is correct
3 Correct 335 ms 12900 KB Output is correct
4 Correct 222 ms 9668 KB Output is correct
5 Correct 484 ms 13276 KB Output is correct
6 Correct 411 ms 13660 KB Output is correct
7 Correct 370 ms 13636 KB Output is correct
8 Correct 265 ms 9760 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 10840 KB Output is correct
2 Correct 84 ms 10800 KB Output is correct
3 Correct 80 ms 10672 KB Output is correct
4 Correct 5 ms 8604 KB Output is correct
5 Correct 175 ms 12168 KB Output is correct
6 Correct 122 ms 12164 KB Output is correct
7 Correct 108 ms 11844 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 8996 KB Output is correct
2 Correct 47 ms 8944 KB Output is correct
3 Correct 86 ms 9924 KB Output is correct
4 Correct 94 ms 9972 KB Output is correct
5 Correct 142 ms 9868 KB Output is correct
6 Correct 126 ms 11192 KB Output is correct
7 Correct 130 ms 10644 KB Output is correct
8 Correct 184 ms 11716 KB Output is correct
9 Correct 627 ms 17800 KB Output is correct
10 Correct 476 ms 13212 KB Output is correct
11 Correct 502 ms 14268 KB Output is correct
12 Correct 635 ms 17324 KB Output is correct
13 Correct 519 ms 17648 KB Output is correct