oj.uz

Submission #54054

# Submission time Handle Problem Language Result Execution time Memory
54054 2018-07-02T09:23:07 Z tmwilliamlin168 Tram (CEOI13_tram) C++14
100 / 100
 456 ms 16748 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pli pair<ll, int>
#define fi first
#define se second

const int mxN=1.5e5, mxM=3e4;
int n, m, p[mxM];
set<int> ors, av;
bool occ[mxN+1][2];

inline pli d2(int a) {
	int b=*ors.upper_bound(a);
	if(a==-1)
		return {(ll)b*b+(!occ[b][0]||!occ[b][1]), occ[b][0]&&!occ[b][1]};
	if(b==n)
		return {(ll)(n-1-a)*(n-1-a)+(!occ[a][0]||!occ[a][1]), 2*(n-1)+(occ[a][0]&&!occ[a][1])};
	ll d=b-a;
	if(d%2==0) {
		if(!(occ[a][0]&&occ[b][1])&&!(occ[a][1]&&occ[b][0]))
			return {(d/2)*(d/2)+1, 2*((a+b)/2)+occ[a][0]};
		return {(d/2)*(d/2), 2*((a+b)/2)};
	}
	int os=occ[a][0]+occ[a][1]+occ[b][0]+occ[b][1];
	if(os!=3)
		return {(d/2)*(d/2)+(os==2), 2*((a+b)/2)+(os==2&&occ[a][0])};
	return {(d/2)*(d/2)+1, 2*((a+b)/2+(occ[a][0]&&occ[a][1]))+(occ[a][0]&&occ[b][0])};
}

struct asicmp {
	inline bool operator()(const int &a, const int &b) const {
		ll da=d2(a).fi, db=d2(b).fi;
		return da==db?a<b:da>db;
	}
};
set<int, asicmp> asis;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	ors.insert(-1);
	ors.insert(n);
	for(int i=0; i<2*n; ++i)
		av.insert(i);
	asis.insert(-1);
	for(int mi=0; mi<m; ++mi) {
		char qt;
		cin >> qt;
		if(qt=='E'||qt=='A') {
			if(qt=='E') {
				p[mi]=*asis.begin();
				pli ad=d2(p[mi]);
				if(ad.fi<=1)
					p[mi]=*av.begin();
				else
					p[mi]=ad.se;
			} else
				cin >> p[mi];
			av.erase(p[mi]);
			auto it=ors.lower_bound(p[mi]/2);
			asis.erase(*--it);
			asis.erase(p[mi]/2);
			occ[p[mi]/2][p[mi]%2]=1;
			ors.insert(p[mi]/2);
			asis.insert(*it);
			asis.insert(p[mi]/2);
			cout << p[mi]/2+1 << " " << p[mi]%2+1 << "\n";
//			for(auto it2=asis.begin(); it2!=asis.end(); ++it2)
//				cout << *it2 << " " << d2(*it2).fi << " " << d2(*it2).se << endl;
		} else {
			int pk;
			cin >> pk, --pk;
			auto it=ors.lower_bound(p[pk]/2);
			asis.erase(*--it);
			asis.erase(p[pk]/2);
			occ[p[pk]/2][p[pk]%2]=0;
			if(occ[p[pk]/2][0]||occ[p[pk]/2][1])
				asis.insert(p[pk]/2);
			else
				ors.erase(p[pk]/2);
			asis.insert(*it);
			av.insert(p[pk]);
		}
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 620 KB Output is correct
2 Correct 8 ms 364 KB Output is correct
3 Correct 7 ms 492 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 620 KB Output is correct
2 Correct 7 ms 364 KB Output is correct
3 Correct 7 ms 492 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 14808 KB Output is correct
2 Correct 8 ms 364 KB Output is correct
3 Correct 73 ms 14700 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 14956 KB Output is correct
2 Correct 7 ms 364 KB Output is correct
3 Correct 84 ms 14828 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 2668 KB Output is correct
2 Correct 209 ms 620 KB Output is correct
3 Correct 242 ms 2468 KB Output is correct

Subtask #8
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 456 ms 16748 KB Output is correct
2 Correct 183 ms 620 KB Output is correct
3 Correct 305 ms 15488 KB Output is correct