Submission #454922

#	Time	Username	Problem	Language	Result	Execution time	Memory
454922		kingfran1907	Cake (CEOI14_cake)	C++14	0 / 100	2099 ms	21884 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 = 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 (stderr)

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--;
      |    ~~~~~^~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 50