Submission #367469

#	Time	Username	Problem	Language	Result	Execution time	Memory
367469		kostia244	Tram (CEOI13_tram)	C++17	0 / 100	56 ms	5864 KiB

tram

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 150001;
int n, m;
multiset<array<int, 3>> pq;
vector<array<int, 2>> lol;
map<int, int> what;
template<class OwO, class It>
void P(It l, It r, OwO uwu) {
	if(++l == what.begin() && r == what.end()) return;
	--l;
	if(r == what.begin()) {
		//cout << "This\n";
		l = what.end();
		if(r->first == 1) {
			if(r->second == 1) uwu(l, r, {1, 2});
			if(r->second == 2) uwu(l, r, {1, 1});
		} else {
			if(r->second == 3) {
				uwu(l, r, {1, 1});
				uwu(l, r,{1, 2});
			}
			if(r->second == 1) {
				uwu(l, r, {1, 2});
			}
			if(r->second == 2) {
				uwu(l, r, {1, 1});
			}
		}
		if(r->first == 2) {
			if(r->second == 1) uwu(l, r, {2, 2});
			if(r->second == 2) uwu(l, r, {2, 1});
		} 
		return;
	}
	if(r == what.end()) {
		//cout << "This 2222\n";
		if(l->first == n) {
			if(l->second == 1) uwu(l, r, {n, 2});
			if(l->second == 2) uwu(l, r, {n, 1});
		} else {
			//cout << n << ":thonkms\n";
			if(l->second == 3) {
				uwu(l, r, {n, 1});
				uwu(l, r, {n, 2});
			}
			if(l->second == 1) {
				uwu(l, r, {n, 2});
			}
			if(l->second == 2) {
				uwu(l, r, {1, 1});
			}
		}
		if(l->first == n-1) {
			if(l->second == 1) uwu(l, r, {n-1, 2});
			if(l->second == 2) uwu(l, r, {n-1, 1});
		} 
		return;
	}
	if(l->second+r->second==3) {
		if((l->first-r->first)%2) {//even
			if(l->first+1 != r->first) {
			int mid = (l->first+r->first)/2;
			uwu(l, r, {mid  , 3^l->second});
			uwu(l, r, {mid+1, 3^r->second});
			}
		} else {//odd
			int mid = (l->first+r->first)/2;
			uwu(l, r, {mid, 1});
			uwu(l, r, {mid, 2});
		}
		if(r->first-l->first < 3) {
			uwu(l, r, {l->first, 3^l->second});
			uwu(l, r, {r->first, 3^r->second});
		}
		return;
	}
	if(min(l->second, r->second) == 3) {
		if(l->first+1 != r->first) {
			int mid = (l->first+r->first)/2;
			uwu(l, r, {mid, 1});
			uwu(l, r, {mid, 2});
		}
		return;
	}
	if(max(l->second, r->second) == 3) {
		int p = l->second != 3 ? l->first : r->first;
		int mn = min(l->second, r->second);
		int mid = (l->first+r->first)/2;
		if(r->first-l->first > 2) {
			if((l->first+r->first)%2) mid += p > mid;
			uwu(l, r, {mid, 3^mn});
		}
		if(r->first-l->first == 2) {
			uwu(l, r, {mid, 1});
			uwu(l, r, {mid, 2});
		}
		if(r->first-l->first <= 2) {
			uwu(l, r, {p, 3^mn});
		}
		return;
	}
	int mid = (l->first+r->first)/2;
	int F = 3^(l->second|r->second);
	if(l->first+1 != r->first) {
	uwu(l, r, {mid, F});
	if((l->first+r->first)%2) {
		mid++;
		uwu(l, r, {mid, F});
	}
	}
}
template<class It>
void add(It l, It r, array<int, 2> x) {
	int d = 1<<30;
	assert(x[1] <= 2);
	for(auto i : {l, r})
	if(i != what.end()) {
		int c = 0;
		if(i->first == x[0]) c = 2;
		else c = abs(i->first-x[0])*2 + abs(i->second-x[1]);
		d = min(d, c);
	}
	pq.insert({d, -x[0], -x[1]});
}
template<class It>
void del(It l, It r, array<int, 2> x) {
	int d = 1<<30;
	for(auto i : {l, r})
	if(i != what.end()) {
		int c = 0;
		if(i->first == x[0]) c = 2;
		else c = abs(i->first-x[0])*2 + abs(i->second-x[1]);
		d = min(d, c);
	}
	pq.erase(pq.find({d, -x[0], -x[1]}));
}
void add() {
	int x, y;
	if(pq.empty()) x = 1, y = 1, lol.push_back({1, 1});
	else {
		auto [di, xx, yy] = *pq.rbegin();xx*=-1,yy*=-1;
		x = xx, y = yy;
		lol.push_back({x, y});
	}
	what[x] += 0;
	auto p = what.find(x);
	auto l = p;--l;
	auto r = p;++r;
	auto DEL = del<decltype(l)>;
	auto ADD = add<decltype(l)>;
	if(p->second == 0) {
		if(what.size() > 1) P(l, r, DEL);
	} else P(l, p, DEL), P(p, r, DEL);
	what[x] += y;
	P(l, p, ADD);
	//cout << "this should produce the interesting stuff\n";
	P(p, r, ADD);
}
void fuck(int id) {
	auto p = what.find(lol[id][0]);
	auto l = p;--l;
	auto r = p;++r;
	auto DEL = del<decltype(l)>;
	auto ADD = add<decltype(l)>;
	P(l, p, DEL), P(p, r, DEL);
	what[lol[id][0]] -= lol[id][1];
	if(what[lol[id][0]] == 0) {
		what.erase(lol[id][0]);
		P(l, r, ADD);
	} else P(l, p, ADD), P(p, r, ADD);
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	int t;
	cin >> n >> m;
	char c;
	while(m--) {
		cin >> c;
		if(c == 'E') add(), cout << lol.back()[0] << " " << lol.back()[1] << '\n';
		else cin >> t, fuck(t-1), lol.push_back({-1, -1});
		continue;
		cout << "QUERIES LEFT : " << m << endl;
		for(auto [d, x, y] : pq) cout << d << "  | " << x << " " << y << " " << endl;
		for(auto [x, y] : what) cout << x << " ~ " << y << endl;
	}
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 15
• Subtask 8: 0 / 20