제출 #567822

#제출 시각아이디문제언어결과실행 시간메모리
567822MilosMilutinovicRoad Construction (JOI21_road_construction)C++14
6 / 100
2222 ms519092 KiB
/** * author: wxhtzdy * created: 24.05.2022 08:24:38 **/ #include <bits/stdc++.h> using namespace std; #define int long long const int MAX = 500000; const int inf = (int) 5e9; int root_u[MAX], root_d[MAX], tsz, ls[30 * MAX], rs[30 * MAX], root; pair<int, int> mx[30 * MAX]; void build(int& node, int l, int r) { node = ++tsz; mx[node] = make_pair(-inf, l); if (l == r) { return; } int mid = l + r >> 1; build(ls[node], l, mid); build(rs[node], mid + 1, r); } void modify(int& node, int pnode, int l, int r, int i, int v) { node = ++tsz; ls[node] = ls[pnode]; rs[node] = rs[pnode]; if (l == r) { mx[node] = make_pair(v, l); return; } int mid = l + r >> 1; if (i <= mid) { modify(ls[node], ls[pnode], l, mid, i, v); } else { modify(rs[node], rs[pnode], mid + 1, r, i, v); } mx[node] = max(mx[ls[node]], mx[rs[node]]); } pair<int, int> query(int node, int l, int r, int ll, int rr) { if (l > r || l > rr || r < ll || ll > rr) { return make_pair(-inf, l); } if (ll <= l && r <= rr) { return mx[node]; } int mid = l + r >> 1; return max(query(ls[node], l, mid, ll, rr), query(rs[node], mid + 1, r, ll, rr)); } signed main() { ios::sync_with_stdio(false); cin.tie(0); int n, k; cin >> n >> k; vector<int> x(n); vector<int> y(n); for (int i = 0; i < n; i++) { cin >> x[i] >> y[i]; } vector<int> xs; for (int i = 0; i < n; i++) { xs.push_back(x[i]); } vector<int> order(n); iota(order.begin(), order.end(), 0); sort(order.begin(), order.end(), [&](int i, int j) { if (x[i] != x[j]) { return x[i] < x[j]; } else { return y[i] < y[j]; } }); vector<int> idx(n); for (int i = 0; i < n; i++) { idx[order[i]] = i; } vector<pair<int, int>> ys; for (int i : order) { ys.emplace_back(y[i], x[i]); } sort(ys.begin(), ys.end()); ys.erase(unique(ys.begin(), ys.end()), ys.end()); mx[0] = make_pair(-inf, 0); build(root, 0, ys.size() - 1); int prv_u = root; int prv_d = root; auto GetId = [&](int i) { return lower_bound(ys.begin(), ys.end(), make_pair(y[i], x[i])) - ys.begin(); }; for (int i : order) { int j = GetId(i); modify(root_u[i], prv_u, 0, ys.size() - 1, j, x[i] + y[i]); modify(root_d[i], prv_d, 0, ys.size() - 1, j, x[i] - y[i]); prv_u = root_u[i]; prv_d = root_d[i]; } set<tuple<int, int, int, int>> st; for (int i = 0; i < n; i++) { int j = GetId(i); { auto val = query(root_u[i], 0, ys.size() - 1, 0, j - 1); st.insert(make_tuple(x[i] + y[i] - val.first, i, val.second, 0)); } { auto val = query(root_d[i], 0, ys.size() - 1, j + 1, ys.size() - 1); st.insert(make_tuple(x[i] - y[i] - val.first, i, val.second, 1)); } } for (int b = 0; b < k; b++) { auto it = st.begin(); cout << get<0>(*it) << '\n'; int i = get<1>(*it); int p = get<2>(*it); int d = get<3>(*it); st.erase(it); if (d == 0) { modify(root_u[i], root_u[i], 0, ys.size() - 1, p, -inf); int j = GetId(i); auto val = query(root_u[i], 0, ys.size() - 1, 0, j - 1); st.insert(make_tuple(x[i] + y[i] - val.first, i, val.second, 0)); } else { modify(root_d[i], root_d[i], 0, ys.size() - 1, p, -inf); int j = GetId(i); auto val = query(root_d[i], 0, ys.size() - 1, j + 1, ys.size() - 1); st.insert(make_tuple(x[i] - y[i] - val.first, i, val.second, 1)); } } return 0; }

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

road_construction.cpp: In function 'void build(long long int&, long long int, long long int)':
road_construction.cpp:23:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |   int mid = l + r >> 1;
      |             ~~^~~
road_construction.cpp: In function 'void modify(long long int&, long long int, long long int, long long int, long long int, long long int)':
road_construction.cpp:36:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |   int mid = l + r >> 1;
      |             ~~^~~
road_construction.cpp: In function 'std::pair<long long int, long long int> query(long long int, long long int, long long int, long long int, long long int)':
road_construction.cpp:52:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |   int mid = l + r >> 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...