Submission #414799

#TimeUsernameProblemLanguageResultExecution timeMemory
414799ja_kingyWalk (CEOI06_walk)C++14
0 / 100
80 ms131076 KiB
#include <bits/stdc++.h> using namespace std; const int mxX = 1e6+5; int n, x, y, ncnt, rt[mxX]; typedef pair<int,int> pii; vector<tuple<int,int,int,int>> boxes[mxX]; struct node{ int lc, rc, lz; pii val; } st[11000000]; int build(int l = -mxX, int r = mxX) { int t = ++ncnt; if (r - l > 1) { int m = (l+r)/2; st[t].lc = build(l, m); st[t].rc = build(m, r); } return t; } void push(int t) { if (st[t].lz) { st[++ncnt] = st[st[t].lc]; st[t].lc = ncnt; st[++ncnt] = st[st[t].rc]; st[t].rc = ncnt; st[st[t].lc].lz = st[st[t].rc].lz = 1; st[t].lz = 0; st[st[t].lc].val = st[st[t].rc].val = st[t].val; } } int upd(int ul, int ur, pii v, int t, int l = -mxX, int r = mxX) { if (ur <= l || r <= ul) return t; st[++ncnt] = st[t]; t = ncnt; if (ul <= l && r <= ur) { st[t].lz = 1; st[t].val = v; return t; } push(t); int m = (l+r)/2; st[t].lc = upd(ul, ur, v, st[t].lc, l, m); st[t].rc = upd(ul, ur, v, st[t].rc, m, r); return t; } pii qry(int x, int t, int l = -mxX, int r = mxX) { if (r - l == 1) return st[t].val; push(t); int m = (l+r)/2; if (x < m) return qry(x, st[t].lc, l, m); else return qry(x, st[t].rc, m, r); } struct line{int pt, m, c;}; bool operator < (line a, line b) { return a.pt < b.pt; } set<line> lines; int qd(int x) { auto l = lines.upper_bound({x,0,0}); l--; return l->m * x + l->c; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> x >> y >> n; rt[0] = build(); lines.insert({-mxX,-1,0}); lines.insert({0,1,0}); for(int i = 0,x1,y1,x2,y2; i < n; ++i) { cin >> x1 >> y1 >> x2 >> y2; if (x1 > x2) swap(x1, x2); if (y1 > y2) swap(y1, y2); boxes[x2+1].push_back({x1, y1, x2, y2}); } for (int tx = 1; tx <= x; ++tx) { rt[tx] = rt[tx-1]; for (auto [x1, y1, x2, y2] : boxes[tx]) { int d1 = qd(y1-1), d2 = qd(y2+1), tp = (d2-d1+y2+y1)/2, tpd = d2+y2+1-tp, oldm = (--lines.upper_bound({y2+1,0,0}))->m; for (auto it = lines.lower_bound({y1-1,0,0}); it != lines.end() && it->pt <= y2+1;) { it = lines.erase(it); } if (y1-1 != tp) lines.insert({y1-1, 1, d1 - (y1-1)}); if (tp != y2+1) lines.insert({tp, -1, tpd + tp}); lines.insert({y2+1, oldm, d2 - (y2+1)*oldm}); rt[tx] = upd(y1, tp, {tx,y1-1}, rt[tx]); rt[tx] = upd(tp, y2+1, {tx,y2+1}, rt[tx]); } } vector<pii> pts, mvs; pii pt = {x,y}; pts.push_back(pt); while (pt != make_pair(0,0)) { pt = qry(pt.second, rt[pt.first]); pts.push_back(pt); } reverse(pts.begin(), pts.end()); for (int i = 0; i < pts.size()-1; ++i) { if (pts[i+1].second != pts[i].second) mvs.push_back({0,pts[i+1].second - pts[i].second}); if (mvs.size() > 1 && mvs.back().first && mvs[mvs.size()-2].first) { int nw = mvs.back().first; mvs.pop_back(); nw += mvs.back().first; mvs.pop_back(); mvs.push_back({nw, 0}); } if (mvs.size() > 1 && mvs.back().second && mvs[mvs.size()-2].second) { int nw = mvs.back().second; mvs.pop_back(); nw += mvs.back().second; mvs.pop_back(); mvs.push_back({0, nw}); } if (pts[i+1].first != pts[i].first) mvs.push_back({pts[i+1].first - pts[i].first,0}); if (mvs.size() > 1 && mvs.back().first && mvs[mvs.size()-2].first) { int nw = mvs.back().first; mvs.pop_back(); nw += mvs.back().first; mvs.pop_back(); mvs.push_back({nw, 0}); } if (mvs.size() > 1 && mvs.back().second && mvs[mvs.size()-2].second) { int nw = mvs.back().second; mvs.pop_back(); nw += mvs.back().second; mvs.pop_back(); mvs.push_back({0, nw}); } } cout << qd(y) + x << '\n'; cout << mvs.size() << '\n'; int zi = -1; for (pii m: mvs) { assert(m.first != 0 || m.second != 0); int nzi = m.first == 0 ? 1 : 2; assert(zi != nzi); zi = nzi; cout << m.first << ' ' << m.second << '\n'; } }

Compilation message (stderr)

walk.cpp: In function 'int main()':
walk.cpp:87:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   87 |         for (auto [x1, y1, x2, y2] : boxes[tx]) {
      |                   ^
walk.cpp:107:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for (int i = 0; i < pts.size()-1; ++i) {
      |                     ~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...