| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 160639 |
2019-10-29T04:15:15 Z |
lyc |
Tram (CEOI13_tram) |
C++14 |
|
102 ms |
4588 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)
const int MX_N = 150005;
const int MX_M = 30005;
struct P {
int a, b; ll v;
bool operator<(const P& p) const {
if (v == p.v) {
if (a == p.a) return b < p.b;
return a < p.a;
}
return v > p.v;
}
};
int N, M;
int A[MX_N];
ii rec[MX_M];
set<P> val;
set<int> occ;
P calc(int l, int r) {
l = max(l,1); r = min(r,N);
int m = (l+r)/2;
P best = {-1,-1,-1};
vector<ii> pts;
if (!(A[l]&2)) pts.emplace_back(l,1);
if (!(A[l]&4)) pts.emplace_back(l,2);
if (l < r) {
if (!(A[m]&2)) pts.emplace_back(m,1);
if (!(A[m]&4)) pts.emplace_back(m,2);
if (!(A[m+1]&2)) pts.emplace_back(m+1,1);
if (!(A[m+1]&4)) pts.emplace_back(m+1,2);
if (!(A[r]&2)) pts.emplace_back(r,1);
if (!(A[r]&4)) pts.emplace_back(r,2);
}
for (auto x : pts) {
auto it = occ.lower_bound(x.fi);
ll cost = 1e18;
if (x.fi == *it) {
cost = 1;
} else {
auto prv = *prev(it), nxt = *it;
if (prv != 0) cost = min(cost, (ll) (prv-x.fi) * (prv-x.fi) + ((A[prv]&(1<<x.sc)) == 0));
if (nxt != N+1) cost = min(cost, (ll) (nxt-x.fi) * (nxt-x.fi) + ((A[nxt]&(1<<x.sc)) == 0));
}
P cur = {x.fi,x.sc,cost};
if (cur < best) best = cur;
}
//cout << "BEST: " << best.a << " " << best.b << " :: " << best.v << endl;
return best;
}
void dbg() {
cout << "==========================================" << endl;
cout << "TRAM: ";
for (auto x : occ) cout << x << ':' << A[x] << ' ';
cout << endl;
cout << "VAL: ";
for (auto x : val) cout << '[' << x.a << ',' << x.b << "]:" << x.v << ' ';
cout << endl;
cout << "==========================================" << endl;
cout << endl;
}
int main() {
//freopen("in.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> M;
occ.insert(0); occ.insert(N+1);
val.insert(calc(0,N+1));
A[0] = A[N+1] = 6;
FOR(i,1,M){
char T; cin >> T;
if (T == 'E') {
auto cur = *val.begin();
auto it = occ.lower_bound(cur.a);
if (cur.a == *it) {
if (it != occ.begin()) val.erase(calc(*prev(it),cur.a));
if (next(it) != occ.end()) val.erase(calc(cur.a,*next(it)));
A[cur.a] |= (1<<cur.b);
if (it != occ.begin()) val.insert(calc(*prev(it),cur.a));
if (next(it) != occ.end()) val.insert(calc(cur.a,*next(it)));
} else {
auto prv = *prev(it), nxt = *it;
val.erase(calc(prv,nxt));
occ.insert(cur.a);
A[cur.a] |= (1<<cur.b);
val.insert(calc(prv,cur.a));
val.insert(calc(cur.a,nxt));
}
cout << cur.a << ' ' << cur.b << '\n';
rec[i] = ii(cur.a, cur.b);
} else {
int P; cin >> P;
auto cur = rec[P];
auto it = occ.find(cur.fi);
auto prv = *prev(it), nxt = *next(it);
val.erase(calc(prv,cur.fi));
val.erase(calc(cur.fi,nxt));
A[cur.fi] &= ~(1<<cur.sc);
if (A[cur.fi] == 0) {
occ.erase(it);
val.insert(calc(prv,nxt));
} else {
val.insert(calc(prv,cur.fi));
val.insert(calc(cur.fi,nxt));
}
}
//dbg();
}
}
| # |
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 |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
492 KB |
Output is correct |
| 2 |
Correct |
4 ms |
364 KB |
Output is correct |
| 3 |
Correct |
3 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
492 KB |
Output is correct |
| 2 |
Correct |
3 ms |
364 KB |
Output is correct |
| 3 |
Correct |
3 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1132 KB |
Output is correct |
| 2 |
Correct |
2 ms |
364 KB |
Output is correct |
| 3 |
Correct |
4 ms |
1004 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1132 KB |
Output is correct |
| 2 |
Correct |
3 ms |
364 KB |
Output is correct |
| 3 |
Correct |
4 ms |
1004 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
70 ms |
2196 KB |
Output is correct |
| 2 |
Correct |
46 ms |
748 KB |
Output is correct |
| 3 |
Correct |
69 ms |
1644 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
102 ms |
4588 KB |
Output is correct |
| 2 |
Correct |
47 ms |
824 KB |
Output is correct |
| 3 |
Correct |
67 ms |
2268 KB |
Output is correct |
