Submission #740369

#TimeUsernameProblemLanguageResultExecution timeMemory
740369finn__Sweeping (JOI20_sweeping)C++17
0 / 100
496 ms72164 KiB
#include <bits/stdc++.h> using namespace std; constexpr size_t M = 500000; uint32_t compare_mode = 0; struct segment { int32_t i1, i2, x1, x2, y1, y2; bool operator<(segment const &s) const { return !compare_mode ? i1 < s.i1 : (compare_mode == 1 ? x1 < s.x1 : y1 > s.y1); } }; set<segment> s; pair<int32_t, int32_t> p[M]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int64_t n, m, q; cin >> n >> m >> q; for (int32_t i = 0; i < m; ++i) { cin >> p[i].first >> p[i].second; segment t = {i, i, p[i].first, p[i].first, p[i].second, p[i].second}; if (!s.empty()) { auto it = --s.end(); if (it->x1 == it->x2 && it->x2 == p[i].first) { t.y2 = it->y2; t.i1 = it->i1; s.erase(it); } else if (it->y1 == it->y2 && it->y2 == p[i].second) { t.x1 = it->x1; t.i1 = it->i1; s.erase(it); } } s.insert(t); } while (q--) { size_t t; cin >> t; if (t == 1) { int32_t i; cin >> i, --i; compare_mode = 0; auto it = prev(s.upper_bound((segment){i, i, 0, 0, 0, 0})); cout << max(it->x1, p[i].first) << ' ' << max(it->y1, p[i].second) << '\n'; } else if (t == 2) { int32_t l; cin >> l; compare_mode = 2; auto it = s.lower_bound((segment){0, 0, 0, 0, l, l}); segment t = {INT32_MAX, -1, n - l, n - l, INT32_MAX, -1}; while (it != s.end() && it->x1 <= n - l) { t.y1 = min(t.y1, it->y1); t.y2 = max(t.y2, it->y2); if (it->x2 <= n - l) { t.i1 = min(t.i1, it->i1); t.i2 = max(t.i2, it->i2); it = s.erase(it); } else { int32_t a = it->i1, b = it->i2; while (a < b) { size_t const mid = (a + b + 1) / 2; if (max(p[mid].first, it->x1) > n - l) b = mid - 1; else a = mid; } t.i1 = min(t.i1, it->i1); t.i2 = max(t.i2, a); if (a != it->i2) { segment u = {a + 1, it->i2, p[a + 1].first, it->x2, it->y1, it->y1}; s.erase(it); s.insert(u); } else { s.erase(it); } break; } } if (t.i1 != INT32_MAX) s.insert(t); } else if (t == 3) { int32_t l; cin >> l; compare_mode = 1; auto it = s.upper_bound((segment){0, 0, l, l, 0, 0}); if (it == s.begin()) continue; --it; segment t = {INT32_MAX, -1, INT32_MAX, -1, n - l, n - l}; while (it->y1 <= n - l) { t.x1 = min(t.x1, it->x1); t.x2 = max(t.x2, it->x2); if (t.y2 <= n - l) { t.i1 = min(t.i1, it->i1); t.i2 = max(t.i2, it->i2); it = s.erase(it); if (it == s.begin()) break; --it; } else { int32_t a = it->i1, b = it->i2; while (a < b) { size_t const mid = (a + b) / 2; if (max(p[mid].second, it->y1) <= n - l) b = mid; else a = mid + 1; } t.i1 = min(t.i1, a); t.i2 = max(t.i2, it->i2); if (a != it->i1) { segment u = {it->i1, a - 1, it->x1, it->x1, it->y1, p[a - 1].second}; s.erase(it); s.insert(u); } else { s.erase(it); } break; } } if (t.i1 != INT32_MAX) s.insert(t); } else { } } }

Compilation message (stderr)

sweeping.cpp: In function 'int main()':
sweeping.cpp:70:43: warning: narrowing conversion of '(n - ((int64_t)l))' from 'int64_t' {aka 'long int'} to 'int32_t' {aka 'int'} [-Wnarrowing]
   70 |             segment t = {INT32_MAX, -1, n - l, n - l, INT32_MAX, -1};
      |                                         ~~^~~
sweeping.cpp:70:50: warning: narrowing conversion of '(n - ((int64_t)l))' from 'int64_t' {aka 'long int'} to 'int32_t' {aka 'int'} [-Wnarrowing]
   70 |             segment t = {INT32_MAX, -1, n - l, n - l, INT32_MAX, -1};
      |                                                ~~^~~
sweeping.cpp:119:58: warning: narrowing conversion of '(n - ((int64_t)l))' from 'int64_t' {aka 'long int'} to 'int32_t' {aka 'int'} [-Wnarrowing]
  119 |             segment t = {INT32_MAX, -1, INT32_MAX, -1, n - l, n - l};
      |                                                        ~~^~~
sweeping.cpp:119:65: warning: narrowing conversion of '(n - ((int64_t)l))' from 'int64_t' {aka 'long int'} to 'int32_t' {aka 'int'} [-Wnarrowing]
  119 |             segment t = {INT32_MAX, -1, INT32_MAX, -1, n - l, n - l};
      |                                                               ~~^~~
#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...