Submission #673696

#TimeUsernameProblemLanguageResultExecution timeMemory
673696LastRoninFire (JOI20_ho_t5)C++17
6 / 100
505 ms43316 KiB
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #include <bits/stdc++.h> #define ll long long #define pb push_back #define f first #define s second #define mp make_pair #define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; const int N = 2e5 + 100; int n, q; ll a[N]; int p[N], r[N]; ll st[6 * N], si[6 * N], sd[6 * N], que[6 * N]; ll ans[6 * N]; bool comp1(int i, int j) { if(st[i] == st[j]) return (i < j); return (st[i] < st[j]); } bool comp2(int i, int j) { if(si[i] == si[j]) return (i < j); return (si[i] < si[j]); } int shift; struct fen { ll t[4 * N] = {0}, t2[4 * N] = {0}; ll sum1 = 0, sum2 = 0; void clear() { sum1 = 0, sum2 = 0; for(int i = 0; i <= 2 * n; i++) t[i] = t2[i] = 0; } void add(ll p, ll z, ll z2) { sum1 += z, sum2 += z2; for(int i = p; i <= 2 * n; i = i|(i + 1)) { t[i] += z; t2[i] += z2; } } pair<ll, ll> get(ll r) { ll s1 = 0, s2 = 0; for(int i = r; i >= 0; i = (i&(i+1)) - 1) { s1 += t[i]; s2 += t2[i]; } return mp(s1, s2); } } ret; int main() { speed; cin >> n >> q; shift = n + 1; deque<int> s; for(int i = 1; i <= n; i++) cin >> a[i]; for(int j = 1; j <= n; j++) { while(s.size() && a[s.back()] < a[j])s.pop_back(); if(s.size())p[j] = s.back(); s.push_back(j); } while(s.size())s.pop_back(); for(int j = n; j >= 1; j--) { r[j] = n + 1; while(s.size() && a[s.back()] <= a[j])s.pop_back(); if(s.size())r[j] = s.back(); s.push_back(j); } int cnt = 1; for(int i = 1, t; i <= n; i++) { // 1 st[cnt] = 1; sd[cnt] = a[i]; si[cnt++] = i; // 2 if(r[i] != n + 1) { st[cnt] = 1 + (r[i] - i); sd[cnt] = -a[i]; si[cnt++] = r[i]; } // 3 if(p[i] != 0) { st[cnt] = 1 + (i - p[i]); sd[cnt] = -a[i]; si[cnt++] = i; //4 if(r[i] != n + 1) { st[cnt] = 1 + (r[i] - p[i]); sd[cnt] = a[i]; si[cnt++] = r[i]; } } } vector<int> sbt; for(int i = 1; i <= n; i++) a[i] += a[i - 1]; for(int i = 1; i <= q; i++) { ll t, l, r; cin >> t >> l >> r; t++; que[cnt] = i; st[cnt] = t; si[cnt++] = r; que[cnt] = -i; st[cnt] = t; si[cnt++] = l - 1; } //kek cnt--; for(int i = 1; i <= cnt; i++) { sbt.pb(i); } vector<int> queries; sort(sbt.begin(), sbt.end(), comp1); for(int i = 0; i < cnt; i++) { int s = sbt[i]; if(que[s]) { ll qt = st[s], qi = si[s], znak = (que[s] < 0 ? -1 : 1); pair<ll, ll> ggg = ret.get(qt - qi + shift); ggg.f = ret.sum1 - ggg.f; ggg.s = ret.sum2 - ggg.s; ans[que[s] * znak] += znak * (qt + 1) * ggg.f; ans[que[s] * znak] -= znak * ggg.s; } else { ret.add(st[s] - si[s] + shift, sd[s], st[s] * sd[s]); } } ret.clear(); sort(sbt.begin(), sbt.end(), comp2); for(int i = 0; i < cnt; i++) { int s = sbt[i]; if(que[s]) { ll qt = st[s], qi = si[s], znak = (que[s] < 0 ? -1 : 1); pair<ll, ll> ggg = ret.get(qt - qi + shift); ans[que[s] * znak] += znak * (qi + 1) * ggg.f; ans[que[s] * znak] -= znak * ggg.s; } else { ret.add(st[s] - si[s] + shift, sd[s], si[s] * sd[s]); } } for(int i = 1; i <= q; i++) cout << ans[i] << "\n"; }

Compilation message (stderr)

ho_t5.cpp: In function 'int main()':
ho_t5.cpp:85:17: warning: unused variable 't' [-Wunused-variable]
   85 |  for(int i = 1, t; i <= n; i++) {
      |                 ^
#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...