제출 #706142

#제출 시각아이디문제언어결과실행 시간메모리
706142LittleCubeRoad Construction (JOI21_road_construction)C++14
65 / 100
10089 ms77420 KiB
#pragma GCC optimize("Ofast,unroll-loops") #include <bits/stdc++.h> #define ll long long #define pll pair<ll, ll> #define F first #define S second using namespace std; ll N, K, bit[750005]; pll p[250005], pp[250005]; void modify(int pos, int val) { for (int i = pos; i <= 3 * N; i += (i & -i)) bit[i] += val; } ll query(int pos) { ll val = 0; for (int i = pos; i > 0; i -= (i & -i)) val += bit[i]; return val; } ll calc(ll L) { vector<tuple<ll, int, int, int>> v; vector<ll> vy; ll res = 0; for (int i = 1; i <= N; i++) { vy.emplace_back(pp[i].S - L); vy.emplace_back(pp[i].S); vy.emplace_back(pp[i].S + L); } vy.emplace_back(-1e12); sort(vy.begin(), vy.end()); vy.resize(unique(vy.begin(), vy.end()) - vy.begin()); for (int i = 1; i <= N; i++) { ll x = pp[i].F, y = pp[i].S, l = lower_bound(vy.begin(), vy.end(), y - L) - vy.begin(), m = lower_bound(vy.begin(), vy.end(), y) - vy.begin(), r = lower_bound(vy.begin(), vy.end(), y + L) - vy.begin(); v.emplace_back(make_tuple(x - L, -1, m, 0)); v.emplace_back(make_tuple(x, 0, l, r)); v.emplace_back(make_tuple(x + L, 1, m, 0)); } sort(v.begin(), v.end()); for (int i = 1; i <= 3 * N; i++) bit[i] = 0; for (auto [x, t, l, r] : v) { if (t == -1) modify(l, 1); else if (t == 1) modify(l, -1); else if (t == 0) { res += query(r) - query(l - 1) - 1; } } return res / 2; } signed main() { cin >> N >> K; for (int i = 1; i <= N; i++) cin >> p[i].F >> p[i].S; for (int i = 1; i <= N; i++) pp[i] = pll(p[i].F + p[i].S, p[i].F - p[i].S); ll L = 1, R = 4'000'000'000; while (L < R) { ll mid = (L + R) / 2; if (calc(mid) < K) L = mid + 1; else R = mid; } L--; vector<tuple<ll, int, ll, ll>> v; vector<ll> ans; set<pll> st; for (int i = 1; i <= N; i++) { ll x = p[i].F + p[i].S, y = p[i].F - p[i].S; v.emplace_back(make_tuple(x - L, -i, y, 0)); v.emplace_back(make_tuple(x, i, y - L, y + L)); v.emplace_back(make_tuple(x + L, i + N, y, 0)); } sort(v.begin(), v.end()); for (auto [x, t, l, r] : v) { if (t < 0) st.insert(pll(l, -t)); else if (t > N) st.erase(pll(l, t - N)); else { auto lter = st.lower_bound(pll(l, 0)), rter = st.upper_bound(pll(r, N + 1)); while (lter != rter) { ll i = lter->S; if (i < t) ans.emplace_back(abs(p[t].F - p[i].F) + abs(p[t].S - p[i].S)); ++lter; } } } sort(ans.begin(), ans.end()); while (ans.size() < K) ans.emplace_back(R); for (ll i : ans) cout << i << '\n'; }

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

road_construction.cpp: In function 'long long int calc(long long int)':
road_construction.cpp:55:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |     for (auto [x, t, l, r] : v)
      |               ^
road_construction.cpp: In function 'int main()':
road_construction.cpp:100:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  100 |     for (auto [x, t, l, r] : v)
      |               ^
road_construction.cpp:120:23: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  120 |     while (ans.size() < K)
      |            ~~~~~~~~~~~^~~
#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...