Submission #455002

#	Time	Username	Problem	Language	Result	Execution time	Memory
455002		kingfran1907	Cake (CEOI14_cake)	C++14	100 / 100	635 ms	17800 KiB

cake

#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 (stderr)

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 / 15
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50