Submission #926318

#	Time	Username	Problem	Language	Result	Execution time	Memory
926318		AdamGS	Fire (JOI20_ho_t5)	C++17	100 / 100	543 ms	88132 KiB

ho_t5

#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
struct pas {
  ll x1, y1, x2, y2, d;
};
const int LIM=2e5+7;
ll T[LIM], dlu[LIM], kon[LIM], wynik[LIM], tr[4*LIM], lazy[4*LIM], N=1;
vector<pair<ll,ll>>V;
vector<pas>dod, pyt;
void spl(int v) {
  tr[2*v]+=lazy[v]/2;
  tr[2*v+1]+=lazy[v]/2;
  lazy[2*v]+=lazy[v]/2;
  lazy[2*v+1]+=lazy[v]/2;
  lazy[v]=0;
}
void upd(int v, ll l, ll r, int a, int b, ll x) {
  if(b<l || r<a) return;
  if(a<=l && r<=b) {
    tr[v]+=(r-l+1)*x;
    lazy[v]+=(r-l+1)*x;
    return;
  }
  if(lazy[v]) spl(v);
  int mid=(l+r)/2;
  upd(2*v, l, mid, a, b, x);
  upd(2*v+1, mid+1, r, a, b, x);
  tr[v]=tr[2*v]+tr[2*v+1];
}
ll cnt(int v, int l, int r, int a, int b) {
  if(b<l || r<a) return 0;
  if(a<=l && r<=b) return tr[v];
  if(lazy[v]) spl(v);
  int mid=(l+r)/2;
  return cnt(2*v, l, mid, a, b)+cnt(2*v+1, mid+1, r, a, b);
}
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int n, q;
  cin >> n >> q;
  while(N<n) N*=2;
  rep(i, n) cin >> T[i];
  vector<int>P;
  for(int i=n-1; i>=0; --i) {
    while(P.size() && T[P.back()]<T[i]) {
      dod.pb({P.back(), P.back()-i, P.back()+dlu[P.back()]-1, P.back()-i+dlu[P.back()]-1, -T[P.back()]});
      V.pb({-i, -(int)dod.size()});
      P.pop_back();
    }
    if(P.size()) dlu[i]=P.back()-i; else dlu[i]=n-i;
    dod.pb({i, 0, i+dlu[i]-1, dlu[i]-1, T[i]});
    V.pb({-i, -(int)dod.size()});
    P.pb(i);
  }
  rep(i, q) {
    ll t, l, r;
    cin >> t >> l >> r; --l; --r;
    pyt.pb({r, t, i, 1, 0});
    V.pb({t-r, pyt.size()});
    if(l!=0) {
      pyt.pb({l-1, t, i, -1, 0});
      V.pb({t-l+1, pyt.size()});
    }
  }
  sort(all(V));
  for(auto i : V) {
    int p=abs(i.nd)-1;
    if(i.nd<0) upd(1, 0, N-1, dod[p].x1, dod[p].x2, dod[p].d);
    else wynik[pyt[p].x2]+=cnt(1, 0, N-1, 0, pyt[p].x1)*pyt[p].y2;
  }
  rep(i, 2*N) tr[i]=lazy[i]=0;
  reverse(all(V));
  for(auto i : V) {
    int p=abs(i.nd)-1;
    if(i.nd<0) upd(1, 0, N-1, dod[p].y1, dod[p].y2, dod[p].d);
    else wynik[pyt[p].x2]+=cnt(1, 0, N-1, 0, pyt[p].y1)*pyt[p].y2;
  }
  rep(i, q) cout << wynik[i] << '\n';
}

• Subtask 1: 1 / 1
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 6 / 6
• Subtask 5: 80 / 80