| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 414806 |
2021-05-31T08:12:37 Z |
ja_kingy |
Walk (CEOI06_walk) |
C++17 |
|
431 ms |
131072 KB |
#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[5000000];
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() {
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
walk.cpp: In function 'int main()':
walk.cpp:105: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]
105 | for (int i = 0; i < pts.size()-1; ++i) {
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
83 ms |
121612 KB |
Output is correct |
| 2 |
Correct |
85 ms |
121604 KB |
Output is correct |
| 3 |
Correct |
87 ms |
121868 KB |
Output is correct |
| 4 |
Correct |
84 ms |
121964 KB |
Output is correct |
| 5 |
Runtime error |
416 ms |
131072 KB |
Execution killed with signal 11 |
| 6 |
Runtime error |
313 ms |
131072 KB |
Execution killed with signal 11 |
| 7 |
Runtime error |
364 ms |
131072 KB |
Execution killed with signal 11 |
| 8 |
Runtime error |
423 ms |
131072 KB |
Execution killed with signal 11 |
| 9 |
Runtime error |
431 ms |
131072 KB |
Execution killed with signal 11 |
| 10 |
Runtime error |
415 ms |
131072 KB |
Execution killed with signal 11 |
