oj.uz

Submission #264488

# Submission time Handle Problem Language Result Execution time Memory
264488 2020-08-14T07:13:26 Z 임성재(#5088) Tram (CEOI13_tram) C++17
100 / 100
 70 ms 5484 KB 
#include<bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(false); cin.tie(0);
#define pre(a) cout << fixed; cout.precision(a);
#define fi first
#define se second
#define em emplace
#define eb emplace_back
#define all(v) (v).begin(), (v).end()
#define mp make_pair

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf = 1e9;
const ll INF = 1e18;

int n, m;
multiset<pair<ll, pll>> S;
multiset<int> X;
pll x[30010];
int q[150010][2];

bool chk(int t) {
	return q[t][0] || q[t][1];
}

ll dist(pll i, pll j) {
	return (i.fi - j.fi) * (i.fi - j.fi) + (i.se - j.se) * (i.se - j.se);
}

ll cost(int l, int r, pll p) {
	if(q[p.fi][p.se]) return 0;

	ll ret = INF;
	if(l >= 1 && q[l][0]) ret = min(ret, dist(mp(l, 0), p));
	if(l >= 1 && q[l][1]) ret = min(ret, dist(mp(l, 1), p));
	if(r <= n && q[r][0]) ret = min(ret, dist(mp(r, 0), p));
	if(r <= n && q[r][1]) ret = min(ret, dist(mp(r, 1), p));

	return ret;
}

pair<ll, pll> Find(int l, int r) {
	ll mx = -INF;
	pll mxi = mp(1, 0);

	for(int i = min(n, max({1, l, (l+r)/2-1})); i <= max(1, min({n, (l+r+1)/2+1, r})); i++) {
		for(int j=0; j<2; j++) {
			if(cost(l, r, mp(i, j)) > mx) {
				mx = cost(l, r, mp(i, j));
				mxi = mp(i, j);
			}
		}
	}

	//cout << l << " " << r << " " << mxi.fi << " " << mxi.se << " " << mx << endl;

	return mp(mx, mp(-mxi.fi, -mxi.se));
}

void in(int t) {
	//cout << "in\n";

	if(X.find(t) == X.end()) {
		int l = *prev(X.lower_bound(t));
		int r = *X.upper_bound(t);

		S.insert(Find(l, r));

		return;
	}


	int l = t;
	int r = *X.upper_bound(t);

	S.insert(Find(l, r));

	l = *prev(X.lower_bound(t));
	r = t;

	S.insert(Find(l, r));
}

void er(int t) {
	if(X.find(t) == X.end()) return;

	//cout << "out\n";

	int l = t;
	int r = *X.upper_bound(t);

	S.erase(Find(l, r));

	l = *prev(X.lower_bound(t));
	r = t;

	S.erase(Find(l, r));
}

int main() {
	fast;

	cin >> n >> m;

	S.insert(mp(inf, mp(-1, 0)));

	X.insert(-inf);
	X.insert(inf);

	for(int i=1; i<=m; i++) {
		string s;
		cin >> s;

		if(s == "E") {
			auto val = *prev(S.end());


			x[i] = val.se;
			x[i].fi *= -1;
			x[i].se *= -1;

			er(x[i].fi);

			if(!chk(x[i].fi)) X.insert(x[i].fi);
			q[x[i].fi][x[i].se] = i;

			in(x[i].fi);

			if(S.find(val) != S.end()) S.erase(val);

			cout << x[i].fi << " " << x[i].se + 1 << "\n";
		}
		else {
			int k;
			cin >> k;

			er(x[k].fi);

			q[x[k].fi][x[k].se] = 0;
			if(!chk(x[k].fi)) X.erase(x[k].fi);
			
			in(x[k].fi);

			x[k] = mp(0, 0);
		}
	}
}

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 3 ms 492 KB Output is correct
2 Correct 3 ms 364 KB Output is correct
3 Correct 2 ms 492 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 2796 KB Output is correct
2 Correct 53 ms 1176 KB Output is correct
3 Correct 42 ms 2012 KB Output is correct

Subtask #8
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 5484 KB Output is correct
2 Correct 45 ms 1132 KB Output is correct
3 Correct 52 ms 3180 KB Output is correct