제출 #935473

#제출 시각아이디문제언어결과실행 시간메모리
935473qwe1rt1yuiop1Advertisement 2 (JOI23_ho_t2)C++14
59 / 100
2086 ms31040 KiB
#include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; vector<int> seg[2], vec[2]; void build(int id, int x, int l, int r) { if (l + 1 == r) { seg[id][x] = l; return; } int mid = (l + r) >> 1; build(id, x << 1, l, mid), build(id, x << 1 | 1, mid, r); if (vec[id][seg[id][x << 1]] <= vec[id][seg[id][x << 1 | 1]]) seg[id][x] = seg[id][x << 1]; else seg[id][x] = seg[id][x << 1 | 1]; } int qry(int id, int x, int l, int r, int ql, int qr) { // cerr << "ok6\n"; // cerr << id << ' ' << x << ' ' << l << ' ' << ql << ' ' << qr << '\n'; if (ql <= l && r <= qr) return seg[id][x]; int mid = (l + r) >> 1; if (qr <= mid) return qry(id, x << 1, l, mid, ql, qr); if (ql >= mid) return qry(id, x << 1 | 1, mid, r, ql, qr); int retl = qry(id, x << 1, l, mid, ql, qr), retr = qry(id, x << 1 | 1, mid, r, ql, qr); if (vec[id][retl] <= vec[id][retr]) return retl; return retr; } void upd(int id, int x, int l, int r, int idx) { if (l + 1 == r) { seg[id][x] = l; return; } int mid = (l + r) >> 1; if (idx < mid) upd(id, x << 1, l, mid, idx); else upd(id, x << 1 | 1, mid, r, idx); if (vec[id][seg[id][x << 1]] <= vec[id][seg[id][x << 1 | 1]]) seg[id][x] = seg[id][x << 1]; else seg[id][x] = seg[id][x << 1 | 1]; } void solve() { int n; cin >> n; vector<pii> v(n); for (auto &[e, x] : v) cin >> x >> e; sort(v.begin(), v.end()); reverse(v.begin(), v.end()); vector<int> tmp; for (auto [e, x] : v) tmp.emplace_back(x); sort(tmp.begin(), tmp.end()); tmp.resize(unique(tmp.begin(), tmp.end()) - tmp.begin()); int c = tmp.size(); vec[0].assign(c, INT_MAX), vec[1] = vec[0]; vector<set<pii>> st[2]; st[0].resize(n); for (int i = 0; i < n; ++i) st[0][i].clear(); st[1] = st[0]; for (int i = 0; i < n; ++i) { auto [e, x] = v[i]; int id = lower_bound(tmp.begin(), tmp.end(), x) - tmp.begin(); vec[0][id] = min(vec[0][id], e + x); st[0][id].emplace(e + x, i); vec[1][id] = min(vec[1][id], e - x); st[1][id].emplace(e - x, i); } seg[0].assign(c * 4 + 10, 0), seg[1] = seg[0]; for (int i : {0, 1}) build(i, 1, 0, c); vector<int> flag(n, 0); int ans = 0; for (int iii = 0; iii < n; ++iii) { if (flag[iii]) continue; flag[iii] = 1; ++ans; auto [e, x] = v[iii]; for (int j = iii + 1; j < n; ++j) { auto [ej, xj] = v[j]; if (e + x >= ej + xj && xj >= x || e - x >= ej - xj && xj <= x) flag[j] = 1; } continue; int xx = lower_bound(tmp.begin(), tmp.end(), x) - tmp.begin(); // st[0][xx].erase({e + x, iii}); // st[1][xx].erase({e - x, iii}); for (int i : {0, 1}) { for (auto [vall, ii] : st[i][xx]) flag[ii] = 1; st[i][xx].clear(); int val = INT_MAX; if (!st[i][xx].empty()) val = st[i][xx].begin()->first; vec[i][xx] = INT_MAX, upd(i, 1, 0, c, xx); } // cerr << "ok1 " << iii << '\n'; while (1) { int id = qry(0, 1, 0, c, xx, c); if (vec[0][id] > e + x) break; auto [val, iiii] = *st[0][id].begin(); // cerr << "ok3 " << iiii << '\n'; flag[iiii] = 1; auto [eeee, xxxx] = v[iiii]; st[0][id].erase({eeee + xxxx, iiii}); st[1][id].erase({eeee - xxxx, iiii}); for (int i : {0, 1}) { int val = INT_MAX; if (!st[i][id].empty()) val = st[i][id].begin()->first; vec[i][id] = INT_MAX, upd(i, 1, 0, c, id); } } // cerr << "ok2 " << iii << '\n'; if (xx > 0) { while (1) { int id = qry(1, 1, 0, c, 0, xx); if (vec[1][id] > e - x) break; auto [val, iiii] = *st[1][id].begin(); // cerr << "ok4 " << iiii << '\n'; flag[iiii] = 1; auto [eeee, xxxx] = v[iiii]; st[0][id].erase({eeee + xxxx, iiii}); st[1][id].erase({eeee - xxxx, iiii}); for (int i : {0, 1}) { int val = INT_MAX; if (!st[i][id].empty()) val = st[i][id].begin()->first; vec[i][id] = INT_MAX, upd(i, 1, 0, c, id); } } } } cout << ans << '\n'; } /* 4 4 2 2 3 3 4 6 5 3 7 10 10 10 7 10 */ signed main() { ios::sync_with_stdio(0); cin.tie(0); solve(); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'void solve()':
Main.cpp:60:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |     for (auto &[e, x] : v)
      |                ^
Main.cpp:66:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |     for (auto [e, x] : v)
      |               ^
Main.cpp:81:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   81 |         auto [e, x] = v[i];
      |              ^
Main.cpp:101:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  101 |         auto [e, x] = v[iii];
      |              ^
Main.cpp:105:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  105 |             auto [ej, xj] = v[j];
      |                  ^
Main.cpp:106:34: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  106 |             if (e + x >= ej + xj && xj >= x || e - x >= ej - xj && xj <= x)
      |                 ~~~~~~~~~~~~~~~~~^~~~~~~~~~
Main.cpp:117:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  117 |             for (auto [vall, ii] : st[i][xx])
      |                       ^
Main.cpp:120:17: warning: variable 'val' set but not used [-Wunused-but-set-variable]
  120 |             int val = INT_MAX;
      |                 ^~~
Main.cpp:131:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  131 |             auto [val, iiii] = *st[0][id].begin();
      |                  ^
Main.cpp:134:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  134 |             auto [eeee, xxxx] = v[iiii];
      |                  ^
Main.cpp:139:21: warning: variable 'val' set but not used [-Wunused-but-set-variable]
  139 |                 int val = INT_MAX;
      |                     ^~~
Main.cpp:153:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  153 |                 auto [val, iiii] = *st[1][id].begin();
      |                      ^
Main.cpp:156:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  156 |                 auto [eeee, xxxx] = v[iiii];
      |                      ^
Main.cpp:161:25: warning: variable 'val' set but not used [-Wunused-but-set-variable]
  161 |                     int val = INT_MAX;
      |                         ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...