Submission #160639

#TimeUsernameProblemLanguageResultExecution timeMemory
160639lycTram (CEOI13_tram)C++14
100 / 100
102 ms4588 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...