제출 #633626

#제출 시각아이디문제언어결과실행 시간메모리
633626Ooops_sorryMeasures (CEOI22_measures)C++14
0 / 100
1565 ms22096 KiB
#include<bits/stdc++.h> using namespace std; mt19937 rnd(51); #define ll long long #define pb push_back #define ld long double const int N = 4e5 + 10; int n, m, d; struct Fenwick { vector<ll> t; Fenwick(int n) { t.resize(n); } void inc(int i, int d) { for (; i < t.size(); i = (i | (i + 1))) { t[i] += d; } } ll get(int r) { ll ans = 0; for (; r >= 0; r = (r & (r + 1)) - 1) { ans += t[r]; } return ans; } ll get(ll l, ll r) { return get(r) - get(l - 1); } } pr(N), sf(N); struct SegTree { vector<int> t; SegTree(int n) { t.resize(4 * n); } void update(int v, int l, int r, int pos, int val) { if (l == r) { t[v] += val; return; } int m = (l + r) / 2; if (pos <= m) { update(2 * v, l, m, pos, val); } else { update(2 * v + 1, m + 1, r, pos, val); } t[v] = t[v * 2] + t[v * 2 + 1]; } int get_ind(int v, int l, int r, int val) { if (l == r) { return l; } int m = (l + r) / 2; if (t[v * 2] >= val) { return get_ind(2 * v, l, m, val); } else { return get_ind(2 * v + 1, m + 1, r, val - t[v * 2]); } } } t(N); set<pair<int,int>> st; vector<pair<int,int>> u; void update_pr(auto it, int x) { if (it == st.begin()) return; auto pre = prev(it); int pos = lower_bound(u.begin(), u.end(), *it) - u.begin(); pr.inc(pos, x * max(0, d - (it->first - pre->first))); } void update_sf(auto it, int x) { if (next(it) == st.end()) return; auto nxt = next(it); int pos = lower_bound(u.begin(), u.end(), *it) - u.begin(); sf.inc(pos, x * max(0, d - (nxt->first - it->first))); } ld get_val(int num) { int pos = t.get_ind(1, 0, N - 1, num); return (ld)max(pr.get(0, pos), sf.get(pos, N - 1)); } ld get_pair_val(int num) { int pos1 = t.get_ind(1, 0, N - 1, num), pos2 = t.get_ind(1, 0, N - 1, num + 1); return (ld)max(pr.get(0, pos1), sf.get(pos2, N - 1)) + (ld)max(0, d - (u[pos2].first - u[pos1].first)) / 2.0; } signed main() { #ifdef LOCAL freopen("input.txt", "r", stdin); #endif // LOCAL ios_base::sync_with_stdio(0); cin.tie(0); int cnt = 0, kol = 0; cin >> n >> m >> d; vector<int> a(n), b(m); for (int i = 0; i < n; i++) { cin >> a[i]; u.pb({a[i], kol}); st.insert({a[i], kol++}); } for (int i = 0; i < m; i++) { cin >> b[i]; u.pb({b[i], kol++}); } sort(u.begin(), u.end()); u.erase(unique(u.begin(), u.end()), u.end()); int sz = u.size(); for (auto it = st.begin(); it != st.end(); it = next(it)) { update_pr(it, 1); update_sf(it, 1); } for (int i = 0; i < n; i++) { int pos = lower_bound(u.begin(), u.end(), make_pair(a[i], cnt)) - u.begin(); t.update(1, 0, N - 1, pos, 1); cnt++; } for (int i = 0; i < m; i++) { auto up = st.upper_bound({b[i], cnt}); if (up != st.end() && up != st.begin()) { update_pr(up, -1); update_sf(prev(up), -1); } st.insert({b[i], cnt}); auto it = st.lower_bound({b[i], cnt}); update_pr(it, 1); update_sf(it, 1); if (next(it) != st.end()) { update_pr(next(it), 1); } if (it != st.begin()) { update_sf(prev(it), 1); } int pos = lower_bound(u.begin(), u.end(), make_pair(b[i], cnt)) - u.begin(); t.update(1, 0, N - 1, pos, 1); ld ans = 1e18; int l = 0, r = st.size(); while (r - l > 2) { int m1 = l + (r - l) / 3, m2 = r - (r - l) / 3; if (get_val(m1) > get_val(m2)) { l = m1; } else { r = m2; } } for (auto a : {l, l + 1, l + 2}) { if (1 <= a && a <= st.size()) { ans = min(ans, get_val(a)); } } l = 0, r = st.size(); while (r - l > 2) { int m1 = l + (r - l) / 3, m2 = r - (r - l) / 3; if (get_pair_val(m1) > get_pair_val(m2)) { l = m1; } else { r = m2; } } for (auto a : {l, l + 1, l + 2}) { if (1 <= a && a + 1 <= st.size()) { ans = min(ans, get_pair_val(a)); } } cout << ans << ' '; cnt++; } return 0; }

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

Main.cpp: In member function 'void Fenwick::inc(int, int)':
Main.cpp:20:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         for (; i < t.size(); i = (i | (i + 1))) {
      |                ~~^~~~~~~~~~
Main.cpp: At global scope:
Main.cpp:70:16: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   70 | void update_pr(auto it, int x) {
      |                ^~~~
Main.cpp:77:16: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   77 | void update_sf(auto it, int x) {
      |                ^~~~
Main.cpp: In function 'int main()':
Main.cpp:153:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |             if (1 <= a && a <= st.size()) {
      |                           ~~^~~~~~~~~~~~
Main.cpp:167:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |             if (1 <= a && a + 1 <= st.size()) {
      |                           ~~~~~~^~~~~~~~~~~~
Main.cpp:114:9: warning: unused variable 'sz' [-Wunused-variable]
  114 |     int sz = u.size();
      |         ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...