제출 #1115467

#제출 시각아이디문제언어결과실행 시간메모리
1115467Zero_OPFire (JOI20_ho_t5)C++14
100 / 100
285 ms56752 KiB
#include <bits/stdc++.h> using namespace std; #define dbg(x) "[" << #x << " = " << (x) << "]" enum event_type { start_decreasing, stop_increasing, become_zero }; struct fenwick_tree{ vector<long long> bit; fenwick_tree(int n) : bit(n + 1, 0) {} void update(int id, long long val){ for(; id < (int)bit.size(); id += id & (-id)) bit[id] += val; } long long query(int id){ long long sum = 0; for(; id > 0; id -= id & (-id)) sum += bit[id]; return sum; } void debug(){ cout << "["; for(int i = 1; i < (int)bit.size(); ++i){ cout << query(i) - query(i - 1); if(i + 1 == (int)bit.size()) cout << "]\n"; else cout << ", "; } } }; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); #ifdef LOCAL freopen("task.inp", "r", stdin); freopen("task.out", "w", stdout); #endif // LOCAL int N, Q; cin >> N >> Q; vector<int> S(N + 1), L(N + 1), R(N + 1), stop_inc(N + 1), start_dec(N + 1); stack<int> st; for(int i = 1; i <= N; ++i){ cin >> S[i]; } for(int i = 1; i <= N; ++i){ while(!st.empty() && S[st.top()] <= S[i]) st.pop(); L[i] = (st.empty() ? -(2 * N + 1) : st.top()); st.push(i); } while(!st.empty()) st.pop(); for(int i = N; i >= 1; --i){ while(!st.empty() && S[st.top()] < S[i]) st.pop(); R[i] = (st.empty() ? + (N + 1) : st.top()); st.push(i); } // for(int i = 1; i <= N; ++i){ // cout << "LR : " << i << " " << L[i] << ' ' << R[i] << '\n'; // } /* - Consider frequency table on ranges Event : Part 1 : Start increasing Part 2, 3 : (i - L[i]) : Start decreasing, (R[i] - i) : Stop increasing (May be 3, 2 or 2, 3) Part 4 : (R[i] - L[i] - 1) Become zero when the first S[j] larger than S[i] reach the stop-increasing point the points for S[i] after T (remember to plus 1) is f(i, S) = max(0, S[i] * min(T, stop_inc[i]) - S[i] * max(0, T - start_dec[i])) For T - start_dec[i] >= 0 => T >= start_dec[i], we can calculate this part by let S[i] * T * cnt_on - S[i] * sum start_dec[pos] ok now we have to handle the case for this equation : min(T, stop_inc[i]) >= max(0, T - start_dec[i]) consider when T < stop_inc[i] => T >= max(0, T - start_dec[i]) <=> T >= T - start_dec[i] (ez) consider when T > stop_inc[i] => stop_inc[i] >= max(0, T - start_dec[i]) <=> stop_inc[i] >= T - start_dec[i] <=> stop_inc[i] + start_dec[i] >= T */ vector<vector<tuple<int, int, int>>> queries(N + 2); for(int i = 0; i < Q; ++i){ int t, l, r; cin >> t >> l >> r; queries[t + 1].emplace_back(l, r, i); } vector<vector<tuple<event_type, int>>> sweep(N + 2); for(int i = 1; i <= N; ++i){ { //start decreasing int t = i - L[i]; start_dec[i] = t; if(1 <= t && t <= N + 1){ sweep[t].emplace_back(start_decreasing, i); } } { //stop increasing int t = R[i] - i; stop_inc[i] = t; if(1 <= t && t <= N + 1){ sweep[t].emplace_back(stop_increasing, i); } } { //become zero int t = start_dec[i] + stop_inc[i] - 1; // cout << "become zero : " << i << " -> " << t << '\n'; if(1 <= t && t <= N + 1){ sweep[t].emplace_back(become_zero, i); } } // cout << i << "(" << start_dec[i] << ", " << stop_inc[i] << ")\n"; } // cout << '\n'; int B = 32 - __builtin_clz(N); vector<vector<int>> prev(B, vector<int>(N + 1, -1)); for(int i = 1; i <= N; ++i){ prev[0][i] = L[i]; } for(int i = 1; i < B; ++i){ for(int j = 1; j <= N; ++j){ prev[i][j] = prev[i - 1][j]; if(prev[i][j] > 0) prev[i][j] = prev[i - 1][prev[i][j]]; } } auto find_exact_value = [&](int i, int t) -> int{ int cur = i; for(int b = B - 1; b >= 0; --b){ if(prev[b][cur] > 0 && i - prev[b][cur] <= t){ cur = prev[b][cur]; } } return cur; }; // vector<long long> answer(Q); // for(int t = 2; t <= N + 1; ++t){ // long long sum = 0; // for(auto [l, r, id] : queries[t]){ // long long sum = 0; // for(int i = l; i <= r; ++i){ // cout << max(0, S[i] * (min(t, stop_inc[i]) - max(0, t - start_dec[i]))) << ' '; // sum += max(0, S[i] * (min(t, stop_inc[i]) - max(0, t - start_dec[i]))); // } // // answer[id] = sum; // } // } // // for(int i = 0; i < Q; ++i) cout << answer[i] << '\n'; fenwick_tree ft1(N), ft2(N), ft3(N), ft4(N); for(int i = 1; i <= N; ++i){ ft1.update(i, S[i]); } vector<long long> answer(Q); for(int t = 1; t <= N + 1; ++t){ // cout << "at : " << t << '\n'; auto calculate_prefix = [&](int r) -> long long{ // cout << dbg(r) << ' '; int pos = find_exact_value(r, t - 1); // cout << dbg(pos) << ' '; long long A = ft1.query(pos - 1); long long B = ft2.query(pos - 1); long long C = ft3.query(pos - 1); long long D = ft4.query(pos - 1); long long sum_part = A * t + B; long long loss_part = D * t - C; int num_inc = L[pos] + t; long long extra_part = 1LL * S[pos] * (r - max(pos, num_inc) + 1); assert(extra_part >= 0); // cout << dbg(sum_part) << dbg(loss_part) << dbg(extra_part) << '\n'; // cout << dbg(A) << dbg(B) << dbg(C) << dbg(D) << '\n'; // cout << dbg(sum_part - loss_part + extra_part) << '\n' << '\n'; return sum_part - loss_part + extra_part; }; for(auto [l, r, i] : queries[t]){ answer[i] = calculate_prefix(r) - (l > 1 ? calculate_prefix(l - 1) : 0); } for(auto [e, i] : sweep[t]){ if(e == start_decreasing){ // cout << "start decreasing : " << i << '\n'; ft3.update(i, 1LL * S[i] * start_dec[i]); ft4.update(i, S[i]); } else if(e == stop_increasing){ // cout << "stop increasing : " << i << '\n'; ft1.update(i, -S[i]); ft2.update(i, 1LL * S[i] * stop_inc[i]); } else if(e == become_zero){ // cout << "become zero : " << i << '\n'; ft2.update(i, -1LL * S[i] * stop_inc[i]); ft3.update(i, -1LL * S[i] * start_dec[i]); ft4.update(i, -S[i]); } else assert(false); } // cout << '\n'; // cout << "that's all\n\n"; } for(int i = 0; i < Q; ++i){ cout << answer[i] << '\n'; } return 0; }

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

ho_t5.cpp: In function 'int main()':
ho_t5.cpp:200:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  200 |         for(auto [l, r, i] : queries[t]){
      |                  ^
ho_t5.cpp:204:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  204 |         for(auto [e, i] : sweep[t]){
      |                  ^
#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...