Submission #544140

#TimeUsernameProblemLanguageResultExecution timeMemory
544140SortingWalk (CEOI06_walk)C++17
0 / 100
158 ms11572 KiB
#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; } } 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"; for(auto [dx, dy]: path) cout << dx << " " << dy << "\n"; }

Compilation message (stderr)

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;
      |         ^~
#Verdict Execution timeMemoryGrader output
Fetching results...