# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
53128 |
2018-06-28T13:54:05 Z |
baactree |
Tram (CEOI13_tram) |
C++17 |
|
51 ms |
10680 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m;
set<int> line;
bool trip[150005][3];
ll l[150005][3];
int cnt[150005];
pair<int, int> p[30005];
priority_queue<pair<ll, pair<int, int> > > pq;
const ll inf = 0x3f3f3f3f3f3f3f3f;
pair<int, int> get_p() {
while (!pq.empty() && l[-pq.top().second.first][-pq.top().second.second] != pq.top().first)pq.pop();
if (pq.empty())return { 1,1 };
pair<int, int> ret = { -pq.top().second.first,-pq.top().second.second };
pq.pop();
return ret;
}
ll dist(ll x1, ll y1, ll x2, ll y2) {
ll x = x2 - x1;
ll y = y2 - y1;
return x * x + y * y;
}
void update(int le, int ri) {
if ((le==0&&ri==n+1)||ri - le <= 1)return;
int x = 0;
if (le == 0) {
x = 1;
l[x][1] = l[x][2] = inf;
for (int i = 1; i <= 2; i++) {
for (int j = 1; j <= 2; j++) {
if (trip[ri][j]) {
l[x][i] = min(l[x][i],dist(x, i, ri, j));
}
}
}
}
else if (ri == n + 1) {
x = n;
l[x][1] = l[x][2] = inf;
for (int i = 1; i <= 2; i++) {
for (int j = 1; j <= 2; j++) {
if (trip[le][j]) {
l[x][i] = min(l[x][i], dist(x, i, le, j));
}
}
}
}
else {
x = (le + ri) / 2;
l[x][1] = l[x][2] = inf;
for (int i = 1; i <= 2; i++) {
for (int j = 1; j <= 2; j++) {
if (trip[ri][j]) {
l[x][i] = min(l[x][i], dist(x, i, ri, j));
}
}
}
for (int i = 1; i <= 2; i++) {
for (int j = 1; j <= 2; j++) {
if (trip[le][j]) {
l[x][i] = min(l[x][i], dist(x, i, le, j));
}
}
}
if ((ri - le) & 1) {
pq.push({ l[x][1],{ -x,-1 } });
pq.push({ l[x][2],{ -x,-2 } });
x++;
l[x][1] = l[x][2] = inf;
for (int i = 1; i <= 2; i++) {
for (int j = 1; j <= 2; j++) {
if (trip[ri][j]) {
l[x][i] = min(l[x][i], dist(x, i, ri, j));
}
}
}
for (int i = 1; i <= 2; i++) {
for (int j = 1; j <= 2; j++) {
if (trip[le][j]) {
l[x][i] = min(l[x][i], dist(x, i, le, j));
}
}
}
}
}
pq.push({ l[x][1],{-x,-1} });
pq.push({ l[x][2],{-x,-2} });
}
void insert(int idx) {
p[idx] = get_p();
cout << p[idx].first << " " << p[idx].second << '\n';
line.insert(p[idx].first);
auto it = line.lower_bound(p[idx].first);
auto le = it;
auto ri = it;
--le;
++ri;
for (int i = max(*le + 1, *it - 1); i <= min(*ri - 1, *it + 1); i++)
l[i][1] = l[i][2] = inf;
if (!cnt[p[idx].first]) {
l[p[idx].first][p[idx].second ^ 3] = 1;
pq.push({ 1,{-p[idx].first,-(p[idx].second ^ 3)} });
}
trip[p[idx].first][p[idx].second] = 1;
cnt[p[idx].first]++;
update(*le, *it);
update(*it, *ri);
}
void dupdate(int le, int ri) {
if (ri - le <= 1)return;
int x = 0;
if (le == 0)x = 1;
else if (ri == n + 1)x = n;
else {
x = (le + ri) / 2;
if ((ri - le) & 1) {
l[x][1] = l[x][2] = inf;
x++;
}
}
l[x][1] = l[x][2] = inf;
}
void erase(int idx) {
trip[p[idx].first][p[idx].second] = 0;
if (!--cnt[p[idx].first]) {
l[p[idx].first][p[idx].second ^ 3] = inf;
auto it = line.lower_bound(p[idx].first);
auto le = it;
auto ri = it;
--le;
++ri;
dupdate(*le, *it);
dupdate(*it, *ri);
update(*le, *ri);
line.erase(it);
}
else {
auto it = line.lower_bound(p[idx].first);
auto le = it;
auto ri = it;
--le;
++ri;
update(*le, *it);
update(*it, *ri);
l[p[idx].first][p[idx].second] = 1;
pq.push({ 1,{-p[idx].first,-p[idx].second} });
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
memset(l, 0x3f, sizeof(l));
cin >> n >> m;
line.insert(0);
line.insert(n + 1);
for (int i = 1; i <= m; i++) {
char t;
cin >> t;
if (t == 'E') {
insert(i);
}
else {
int x;
cin >> x;
erase(x);
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
3820 KB |
Output is correct |
2 |
Correct |
2 ms |
3820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
3948 KB |
Output is correct |
2 |
Correct |
3 ms |
3820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4076 KB |
Output is correct |
2 |
Correct |
3 ms |
3948 KB |
Output is correct |
3 |
Correct |
4 ms |
4076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4076 KB |
Output is correct |
2 |
Correct |
3 ms |
3948 KB |
Output is correct |
3 |
Correct |
5 ms |
4076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5100 KB |
Output is correct |
2 |
Correct |
4 ms |
3948 KB |
Output is correct |
3 |
Correct |
4 ms |
5100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
5100 KB |
Output is correct |
2 |
Correct |
4 ms |
3948 KB |
Output is correct |
3 |
Correct |
5 ms |
5100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
5568 KB |
Output is correct |
2 |
Correct |
23 ms |
4460 KB |
Output is correct |
3 |
Correct |
33 ms |
5612 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
45 ms |
10680 KB |
Output is correct |
2 |
Correct |
22 ms |
4460 KB |
Output is correct |
3 |
Correct |
51 ms |
6564 KB |
Output is correct |