Submission #677174

#	Time	Username	Problem	Language	Result	Execution time	Memory
677174		mdubaisi	Cake (CEOI14_cake)	C++14	0 / 100	3 ms	644 KiB

cake

#include <bits/stdc++.h>
//#include <iostream>
//#include <algorithm>
//#include <vector>
//#include <set>
//#include <queue>
//#include <array>
#define ll long long
#define all(v) (v.begin()), (v.end())
#define setall(a, val) for(auto& x : a) x = val
clock_t start_time;
double get_time() { return (double)(clock() - start_time) / CLOCKS_PER_SEC; }
void init() {
#ifndef ONLINE_JUDGE
	FILE* _ = freopen("in.txt", "r", stdin);
	start_time = clock();
#endif
}
const ll MOD = 1e9 + 7;
const ll N = 3e5 + 7;
const ll M = 1e6 + 7;
using namespace std;
//####################################################################################

int t[N];
int n, s;
vector<int> v;
bool vis[N];
void update() {
	priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > p;
	p.push({ v[s], s });
	int tm = 0;
	while (p.size()) {
		int i = p.top().second, x = p.top().first;
		p.pop();

		if (vis[i])
			continue;
		t[i] = tm;
		vis[i] = 1;
		tm++;

		if (i + 1 <= n)
			p.push({ v[i + 1], i + 1 });
		if (i - 1 > 0)
			p.push({ v[i - 1], i - 1 });
	}

	setall(vis, 0);
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); init(); srand(time(0));

	cin >> n >> s;
	v.resize(n + 1);
	set< pair<int, int> > st;
	for (int i = 1; i <= n; i++)
		cin >> v[i], st.insert({ v[i], i });
	update();

	int q;
	cin >> q;
	while (q--) {
		char c; int idx;
		cin >> c >> idx;
		if (c == 'F')
			cout << t[idx] << endl;
		else {
			int pos;
			cin >> pos;
			
			vector< pair<int, int> > add;
			auto it = --st.end();
			int a = (*it).first, b = (*it).second;
			while (--pos) {
				add.push_back({ a + 1, b });
				st.erase(it);
				v[b]++;

				it = --st.end();
				a = (*it).first, b = (*it).second;
			}
			st.erase({ v[idx], idx });
			st.insert({ a + 1, idx });
			v[idx] = a + 1;
			
			for (pair<int, int> p : add)
				st.insert(p);

			update();
		}
	}

	cerr << get_time() << "s" << endl;
}

Compilation message (stderr)

cake.cpp: In function 'void init()':
cake.cpp:15:8: warning: unused variable '_' [-Wunused-variable]
   15 |  FILE* _ = freopen("in.txt", "r", stdin);
      |        ^
cake.cpp: In function 'void update()':
cake.cpp:34:27: warning: unused variable 'x' [-Wunused-variable]
   34 |   int i = p.top().second, x = p.top().first;
      |                           ^

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