#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> void check_min(T &a, const T &b){ a = (a < b) ? a : b; }
template<class T> void check_max(T &a, const T &b){ a = (a > b) ? a : b; }
#define all(x) (x).begin(), (x).end()
const int N = 2e6 + 17;
const int ADD = 1e6 + 3;
const ll INF = 1e18;
int x, y, n, mid[N];
array<int, 4> b[N];
vector<array<int, 3>> sweepline;
struct SegmentTree{
pair<ll, ll> lp[4 * N];
void push_lazy(int i, int l, int r){
if(l == r) return;
if(!lp[i].first && !lp[i].second) return;
lp[2 * i + 1].second = lp[i].second;
lp[2 * i + 2].second = lp[i].second;
lp[2 * i + 1].first = lp[i].first;
int mid = (l + r) >> 1;
lp[2 * i + 2].first = lp[i].first + (mid + 1 - l) * lp[i].second;
lp[i].first = 0;
lp[i].second = 0;
}
void update(int sl, int sr, ll start, ll incr, int i = 0, int l = 0, int r = N - 1){
push_lazy(i, l, r);
if(sr < l || r < sl) return;
if(sl <= l && r <= sr){
lp[i].first = start + (l - sl) * incr;
lp[i].second = incr;
push_lazy(i, l, r);
return;
}
int mid = (l + r) >> 1;
update(sl, sr, start, incr, 2 * i + 1, l, mid);
update(sl, sr, start, incr, 2 * i + 2, mid + 1, r);
}
ll query(int s_idx, int i = 0, int l = 0, int r = N - 1){
push_lazy(i, l, r);
if(s_idx < l || r < s_idx) return 0;
if(l == r) return lp[i].first;
int mid = (l + r) >> 1;
return query(s_idx, 2 * i + 1, l, mid) + query(s_idx, 2 * i + 2, mid + 1, r);
}
} st;
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> x >> y >> n;
y += ADD;
for(int i = 0; i < n; ++i){
for(int j = 0; j < 4; ++j)
cin >> b[i][j];
b[i][1] += ADD;
b[i][3] += ADD;
if(b[i][1] > b[i][3])
swap(b[i][1], b[i][3]);
if(b[i][0] > b[i][2])
swap(b[i][0], b[i][2]);
sweepline.push_back({b[i][0], 1, i});
sweepline.push_back({b[i][2], 2, i});;
}
sweepline.push_back({x, 0, y});
sort(all(sweepline));
st.update(0, ADD, ADD, -1);
st.update(ADD, N - 1, 0, 1);
int pr = 0;
int i;
for(i = 0; i < sweepline.size(); ++i){
auto &e = sweepline[i];
if(e[1] == 0){
break;
}
auto [x, type, idx] = e;
if(type == 1){
st.update(b[idx][1], b[idx][3], INF, 0);
}
else{
int l = st.query(b[idx][1] - 1);
int r = st.query(b[idx][3] + 1);
auto calc_mid = [](int l, int r, int sl, int sr){
if(l <= r)
return (sl + (r - l) + sr) / 2;
return (sl + sr - (l - r) + 1) / 2;
};
mid[idx] = calc_mid(l, r, b[idx][1] - 1, b[idx][3] + 1);
if(b[idx][1] <= mid[idx])
st.update(b[idx][1], mid[idx], l + 1, 1);
if(mid[idx] + 1 <= b[idx][3]){
int start = r - mid[idx] + b[idx][3];
st.update(mid[idx] + 1, b[idx][3], start, -1);
}
}
pr = x;
}
ll ans = st.query(y) + x;
int curr_x = x, curr_y = y;
vector<pair<int, int>> path;
for(--i; i >= 0; --i){
auto [x, type, idx] = sweepline[i];
if(type == 1) continue;
if(b[idx][1] <= curr_y && curr_y <= b[idx][3]){
if(curr_x - x - 1 > 0)
path.push_back({curr_x - x - 1, 0});
int y;
if(curr_y <= mid[idx])
y = b[idx][1] - 1;
else
y = b[idx][3] + 1;
path.push_back({0, curr_y - y});
curr_y = y;
curr_x = x + 1;
}
}
if(curr_x)
path.push_back({curr_x, 0});
if(curr_y != ADD)
path.push_back({0, curr_y - ADD});
reverse(all(path));
cout << ans << "\n";
cout << path.size() << "\n";
for(auto [dx, dy]: path)
cout << dx << " " << dy << "\n";
}
Compilation message
walk.cpp: In function 'int main()':
walk.cpp:88:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for(i = 0; i < sweepline.size(); ++i){
| ~~^~~~~~~~~~~~~~~~~~
walk.cpp:86:9: warning: variable 'pr' set but not used [-Wunused-but-set-variable]
86 | int pr = 0;
| ^~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1748 KB |
Output is correct |
| 4 |
Correct |
3 ms |
1748 KB |
Output is correct |
| 5 |
Correct |
144 ms |
9348 KB |
Output is correct |
| 6 |
Correct |
51 ms |
6648 KB |
Output is correct |
| 7 |
Correct |
78 ms |
3260 KB |
Output is correct |
| 8 |
Correct |
130 ms |
5380 KB |
Output is correct |
| 9 |
Correct |
160 ms |
9656 KB |
Output is correct |
| 10 |
Correct |
157 ms |
8848 KB |
Output is correct |
