제출 #742951

#제출 시각아이디문제언어결과실행 시간메모리
742951GrindMachineRoad Construction (JOI21_road_construction)C++17
100 / 100
9197 ms203080 KiB
// Om Namah Shivaya #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long int ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL) #define pb push_back #define endl '\n' #define sz(a) a.size() #define setbits(x) __builtin_popcountll(x) #define ff first #define ss second #define conts continue #define ceil2(x, y) ((x + y - 1) / (y)) #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define yes cout << "Yes" << endl #define no cout << "No" << endl #define rep(i, n) for(int i = 0; i < n; ++i) #define rep1(i, n) for(int i = 1; i <= n; ++i) #define rev(i, s, e) for(int i = s; i >= e; --i) #define trav(i, a) for(auto &i : a) template<typename T> void amin(T &a, T b) { a = min(a, b); } template<typename T> void amax(T &a, T b) { a = max(a, b); } #ifdef LOCAL #include "debug.h" #else #define debug(x) 42 #endif /* */ const int MOD = 1e9 + 7; const int N = 1e5 + 5; const int inf1 = int(1e9) + 5; const ll inf2 = ll(1e18) + 5; template<typename T> struct fenwick { int siz; vector<T> tree; fenwick(int n) { siz = n; tree = vector<T>(n + 1); } int lsb(int x) { return x & -x; } void build(vector<T> &a, int n) { for (int i = 1; i <= n; ++i) { int par = i + lsb(i); tree[i] += a[i]; if (par <= siz) { tree[par] += tree[i]; } } } void pupd(int i, T v) { i++; while (i <= siz) { tree[i] += v; i += lsb(i); } } T sum(int i) { i++; T res = 0; while (i) { res += tree[i]; i -= lsb(i); } return res; } T query(int l, int r) { if (l > r) return 0; T res = sum(r) - sum(l - 1); return res; } }; template<typename T> struct segtree { // https://codeforces.com/blog/entry/18051 /*=======================================================*/ struct data { vector<pll> a; }; data neutral = data(); data merge(data &left, data &right) { data curr; auto &v1 = left.a, &v2 = right.a, &v3 = curr.a; ll n = sz(v1), m = sz(v2); ll ptr1 = 0, ptr2 = 0; while (ptr1 < n and ptr2 < m) { if (v1[ptr1] <= v2[ptr2]) { v3.pb(v1[ptr1++]); } else { v3.pb(v2[ptr2++]); } } for (; ptr1 < n; ++ptr1) { v3.pb(v1[ptr1]); } for (; ptr2 < m; ++ptr2) { v3.pb(v2[ptr2]); } return curr; } void create(int i, T v) { tr[i].a = v; } void modify(int i, T v) { } /*=======================================================*/ int n; vector<data> tr; segtree() { } segtree(int siz) { init(siz); } void init(int siz) { n = siz; tr.assign(2 * n, neutral); } void build(vector<T> &a, int siz) { rep(i, siz) create(i + n, a[i]); rev(i, n - 1, 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]); } void pupd(int i, T v) { modify(i + n, v); for (i = (i + n) >> 1; i; i >>= 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]); } vector<pll> query(int l, int r, ll mn, ll mx) { pll px = {mn, -inf2}; vector<pll> res; for (l += n, r += n; l <= r; l >>= 1, r >>= 1) { if (l & 1) { auto &v = tr[l++].a; auto it = upper_bound(all(v), px); for (; it != v.end() and it->first <= mx; ++it) { res.pb(*it); } } if (!(r & 1)) { auto &v = tr[r--].a; auto it = upper_bound(all(v), px); for (; it != v.end() and it->first <= mx; ++it) { res.pb(*it); } } } return res; } }; void solve(int test_case) { ll n, k; cin >> n >> k; vector<pll> a(n); rep(i, n) cin >> a[i].ff >> a[i].ss; rep(i, n) { auto [x, y] = a[i]; a[i] = {x + y, x - y}; } vector<ll> b; rep(i, n) b.pb(a[i].ss); sort(all(b)); b.resize(unique(all(b)) - b.begin()); ll siz = sz(b); vector<array<ll, 3>> inds(n); auto get_cnt = [&](ll m) { rep(i, n) { auto [x, y] = a[i]; inds[i][0] = lower_bound(all(b), y - m) - b.begin(); inds[i][1] = lower_bound(all(b), y) - b.begin(); inds[i][2] = upper_bound(all(b), y + m) - b.begin() - 1; } vector<array<ll, 3>> events; rep(i, n) { auto [x, y] = a[i]; events.pb({x, 0, i}); } rep(i, n) { auto [x, y] = a[i]; events.pb({x - m - 1, 1, i}); events.pb({x + m, 2, i}); } sort(all(events)); fenwick<ll> fenw(siz + 5); ll res = 0; for (auto [x, t, i] : events) { if (t == 0) { fenw.pupd(inds[i][1], 1); } else { ll c = 1; if (t == 1) c = -1; ll lx = inds[i][0], rx = inds[i][2]; res += fenw.query(lx, rx) * c; } } res -= n; res /= 2; return res; }; ll l = 0, r = 5e9; ll mx_cost = inf2; while (l <= r) { ll mid = (l + r) >> 1; if (get_cnt(mid) <= k) { mx_cost = mid; l = mid + 1; } else { r = mid - 1; } } b.clear(); rep(i, n) { auto [x, y] = a[i]; b.pb(x - mx_cost), b.pb(x), b.pb(x + mx_cost); } sort(all(b)); b.resize(unique(all(b)) - b.begin()); siz = sz(b); vector<vector<pll>> here(siz); rep(i, n) { auto [x, y] = a[i]; ll ind = lower_bound(all(b), x) - b.begin(); here[ind].pb({y, x}); } rep(i, siz) sort(all(here[i])); segtree<vector<pll>> st(siz + 5); st.build(here, siz); vector<ll> ans; rep(i, n) { auto [x, y] = a[i]; ll lx = lower_bound(all(b), x - mx_cost) - b.begin(); ll rx = lower_bound(all(b), x + mx_cost) - b.begin(); ll mny = y - mx_cost; ll mxy = y + mx_cost; auto v = st.query(lx, rx, mny, mxy); for (auto [y2, x2] : v) { if (x == x2 and y == y2) conts; ll cost = max(abs(x - x2), abs(y - y2)); ans.pb(cost); } } sort(all(ans)); vector<ll> ans2; for (int i = 0; i < sz(ans); i += 2) { assert(ans[i] == ans[i + 1]); ans2.pb(ans[i]); } ans = ans2; while (sz(ans) < k) ans.pb(mx_cost + 1); trav(x, ans) cout << x << endl; } int main() { fastio; int t = 1; // cin >> t; rep1(i, t) { solve(i); } return 0; }

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

road_construction.cpp: In function 'void solve(int)':
road_construction.cpp:337:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  337 |     for (int i = 0; i < sz(ans); i += 2) {
      |                       ^
road_construction.cpp:343:20: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
  343 |     while (sz(ans) < k) ans.pb(mx_cost + 1);
      |                    ^
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...