| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 261470 |
2020-08-11T18:34:49 Z |
Sorting |
Tram (CEOI13_tram) |
C++17 |
|
41 ms |
5868 KB |
#include <bits/stdc++.h>
using namespace std;
const int k_N = 15e4 + 3;
const int k_M = 3e4 + 3;
const long long k_Inf = 1.1e18;
int n, m;
pair<int, int> p[k_M];
int p_cnt = 0;
struct Node{
long long len;
int x, y;
Node(){}
Node(long long len, int x, int y):len(len), x(x), y(y){}
friend bool operator<(const Node &lvalue, const Node &rvalue){
if(lvalue.len != rvalue.len) return lvalue.len > rvalue.len;
if(lvalue.x != rvalue.x) return lvalue.x < rvalue.x;
return lvalue.y < rvalue.y;
}
};
set<pair<int,int>> pos;
set<Node> s;
Node get_node_1(pair<int, int> t){
//cout << t.first << " " << t.second << " t" << "\n";
assert(t.second == 1 || t.second == 2);
return {1, t.first, 3 - t.second};
}
Node get_node_2(pair<long long, int> l, pair<long long, int> r){
auto [lf, ls] = l;
auto [rf, rs] = r;
if(lf + 1 == rf) return {0, -1, -1};
if(lf == 0){
if(rs == 1) return {(rf - 1) * (rf - 1) + 1, 1, 2};
else if(rs == 2) return {(rf - 1) * (rf - 1) + 1, 1, 1};
else return {(rf - 1) * (rf - 1), 1, 1};
}
if(rf == n + 1){
if(ls == 1) return {(n - lf) * (n - lf) + 1, n, 2};
else if(ls == 2) return {(n - lf) * (n - lf) + 1, n, 1};
else return {(n - lf) * (n - lf), n, 1};
}
int mid = (rf + lf) / 2;
if((rf - lf) % 2 == 0){
if((ls | rs) == 3) return {(rf - mid) * (rf - mid), mid, 1};
else if(ls == 2) return {(rf - mid) * (rf - mid) + 1, mid, 1};
else return {(rf - mid) * (rf - mid) + 1, mid, 2};
}
else{
if(ls != 3) return {(mid - lf) * (mid - lf) + 1, mid, (3 - ls)};
else if(rs != 3) return {(rf - (mid + 1)) * (rf - (mid + 1)) + 1, mid + 1, (3 - rs)};
else return {(mid - lf) * (mid - lf), mid, 1};
}
}
pair<int, int> add(){
Node nd = *s.begin();
s.erase(nd);
//cout << "nd - " << nd.x << " " << nd.y << "\n";
auto it = pos.find({nd.x, 3 - nd.y});
if(it != pos.end()){
it--;
auto prev = *it;
it++;
auto curr = *it;
it++;
auto nxt = *it;
it--;
pos.erase(curr);
s.erase(get_node_2(prev, curr));
s.erase(get_node_2(curr, nxt));
pair<int, int> new_curr = {nd.x, 3};
pos.insert(new_curr);
s.insert(get_node_2(prev, new_curr));
s.insert(get_node_2(new_curr, nxt));
}
else{
auto it = pos.insert({nd.x, nd.y}).first;
pair<int, int> curr = *it;
it--;
auto prev = *it;
it++, it++;
auto nxt = *it;
s.erase(get_node_2(prev, nxt));
s.insert(get_node_2(prev, curr));
s.insert(get_node_2(curr, nxt));
s.insert(get_node_1(curr));
}
return {nd.x, nd.y};
}
void remove(pair<int, int> place){
//cout << "remove " << place.first << " " << place.second << "\n";
auto it = pos.find(place);
if(it == pos.end()){
it = pos.find({place.first, 3});
it--;
auto prev = *it;
it++;
auto curr = *it;
it++;
auto nxt = *it;
pos.erase({place.first, 3});
pos.insert({place.first, 3 - place.second});
pair<int, int> new_curr = {place.first, 3 - place.second};
s.erase(get_node_2(prev, curr));
s.erase(get_node_2(curr, nxt));
s.insert(get_node_2(prev, new_curr));
s.insert(get_node_2(new_curr, nxt));
s.insert(get_node_1(new_curr));
}
else{
it--;
auto prev = *it;
it++;
auto curr = *it;
it++;
auto nxt = *it;
//cout << "prev: " << prev.first << " " << prev.second << "\n";
//cout << "curr: " << curr.first << " " << curr.second << "\n";
//cout << "nxt: " << nxt.first << " " << nxt.second << "\n";
pos.erase(curr);
s.erase(get_node_2(prev, curr));
s.erase(get_node_2(curr, nxt));
s.erase(get_node_1(curr));
s.insert(get_node_2(prev, nxt));
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
pos.insert({0, 3});
pos.insert({n + 1, 3});
s.insert(get_node_2({0, 3}, {n + 1, 3}));
for(int i = 1; i <= m; ++i){
char type;
cin >> type;
if(type == 'E'){
p[i] = add();
cout << p[i].first << " " << p[i].second << "\n";
}
else{
int idx;
cin >> idx;
remove(p[idx]);
}
/*cout << "\ns:\n";
for(auto &t: s)
cout << t.len << " - " << t.x << " " << t.y << "\n";
cout << "\npos\n";
for(auto &t: pos)
cout << t.first << " " << t.second << "\n";
cout <<"\n";*/
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
368 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
492 KB |
Output is correct |
| 2 |
Correct |
3 ms |
364 KB |
Output is correct |
| 3 |
Correct |
2 ms |
492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
492 KB |
Output is correct |
| 2 |
Correct |
2 ms |
416 KB |
Output is correct |
| 3 |
Correct |
3 ms |
492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
620 KB |
Output is correct |
| 2 |
Correct |
2 ms |
364 KB |
Output is correct |
| 3 |
Correct |
2 ms |
492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
620 KB |
Output is correct |
| 2 |
Correct |
2 ms |
364 KB |
Output is correct |
| 3 |
Correct |
2 ms |
492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
2284 KB |
Output is correct |
| 2 |
Correct |
32 ms |
748 KB |
Output is correct |
| 3 |
Correct |
29 ms |
1900 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
5868 KB |
Output is correct |
| 2 |
Correct |
26 ms |
748 KB |
Output is correct |
| 3 |
Correct |
40 ms |
2156 KB |
Output is correct |
