Submission #372364

#TimeUsernameProblemLanguageResultExecution timeMemory
372364crackersamdjamFire (JOI20_ho_t5)C++17
1 / 100
65 ms33004 KiB
#include <bits/stdc++.h> #define all(x) (x).begin(), (x).end() using namespace std; using ll = long long; const int MM = 2e5+5, NN = 500, SZ = 300, LOG = 18; struct query{ int t, l, r, id; bool operator<(const query &o) const{ return t < o.t; } } q[MM]; int n, qs; ll a[MM], ans[MM], sp[LOG][MM]; ll qu(int l, int r){ int k = __lg(r-l+1); return max(sp[k][l], sp[k][r-(1<<k)+1]); } stack<pair<int, ll>> st; vector<pair<int, ll>> slope[NN]; ll curslope[NN], cursum[NN]; //at time i, slope changes by x //changes sum by something int ls[MM], rs[MM]; //rs how far will cover //ls how far until covered int main(){ ios_base::sync_with_stdio(0); cin.tie(0); memset(ls, -0x3f, sizeof ls); cin>>n>>qs; for(int i = 1; i <= n; i++){ cin>>a[i]; sp[0][i] = a[i]; ll last = 0; while(size(st) and st.top().second <= a[i]){ auto [j, v] = st.top(); st.pop(); rs[j] = i; } if(size(st)){ auto [j, v] = st.top(); ls[i] = j; } st.emplace(i, a[i]); } while(size(st)){ auto [j, v] = st.top(); st.pop(); rs[j] = n+1; } for(int i = 1; i <= n; i++){ //this one overwrites slope[i/SZ].emplace_back(i-i, a[i]); slope[rs[i]/SZ].emplace_back(rs[i]-i, -a[i]); for(int j = i/SZ; j <= rs[i]/SZ; j++){ if(j != i/SZ){ //start slope[j].emplace_back(j*SZ-i, a[i]); } if(j != rs[i]/SZ){ //end slope[j].emplace_back(j*SZ+SZ-i, -a[i]); } } //when another starts to cover a[i] //and when it ends covering a[i] // i-ls[i] to rs[i]-ls[i] slope[i/SZ].emplace_back(i-ls[i], -a[i]); slope[rs[i]/SZ].emplace_back(rs[i]-ls[i], a[i]); for(int j = i/SZ; j <= rs[i]/SZ; j++){ if(j != i/SZ){ //start slope[j].emplace_back(j*SZ-ls[i], -a[i]); } if(j != rs[i]/SZ){ //end slope[j].emplace_back(j*SZ+SZ-ls[i], a[i]); } } } for(int k = 1; k < LOG; k++){ for(int i = 0; i+(1<<k)-1 <= n; i++){ sp[k][i] = max(sp[k-1][i], sp[k-1][i+(1<<(k-1))]); } } for(int i = 0; i <= n/SZ; i++){ sort(all(slope[i])); reverse(all(slope[i])); } for(int i = 0; i < qs; i++){ cin>>q[i].t>>q[i].l>>q[i].r; q[i].id = i; } sort(q, q+qs); int t = -1; for(int tt = 0; tt < qs; tt++){ auto [nt, l, r, id] = q[tt]; for(int j = t+1; j <= nt; j++){ for(int i = 0; i <= n/SZ; i++){ while(size(slope[i]) and slope[i].back().first <= j){ curslope[i] += slope[i].back().second; slope[i].pop_back(); } cursum[i] += curslope[i]; } } t = nt; r++; int li = ((l+SZ-1)/SZ), ri = ((r)/SZ); if(li >= ri){ for(int i = l; i < r; i++) ans[id] += qu(max(1, i-t), i); } else{ for(int i = l; i < li*SZ; i++) ans[id] += qu(max(1, i-t), i); for(int i = ri*SZ; i < r; i++) ans[id] += qu(max(1, i-t), i); for(int i = li; i < ri; i++) ans[id] += cursum[i]; } } for(int i = 0; i < qs; i++) cout<<ans[i]<<'\n'; }

Compilation message (stderr)

ho_t5.cpp: In function 'int main()':
ho_t5.cpp:42:6: warning: unused variable 'last' [-Wunused-variable]
   42 |   ll last = 0;
      |      ^~~~
#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...