Submission #928638

#	Time	Username	Problem	Language	Result	Execution time	Memory
928638		AdamGS	Dungeon 3 (JOI21_ho_t5)	C++17	100 / 100	390 ms	88152 KiB

Main

#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()
const ll INF=1e9+7;
const int LIM=2e5+7;
ll A[LIM], B[LIM], lewo[LIM], prawo[LIM], wynik[LIM], indl[LIM], indr[LIM], trma[4*LIM], N=1;
vector<pair<pair<ll,ll>,pair<ll,ll>>>V;
vector<int>L[LIM], R[LIM];
pair<pair<ll,ll>,ll>pyt[LIM];
pair<ll,ll>tr[4*LIM];
pair<ll,ll>dodaj(pair<ll,ll>a, pair<ll,ll>b) {
  return {a.st+b.st, a.nd+b.nd};
}
void upd(int v, pair<ll,ll>x) {
  v+=N;
  while(v) {
    tr[v]=dodaj(tr[v], x);
    v/=2;
  }
}
pair<ll,ll>cnt(int l, int r) {
  l+=N; r+=N;
  pair<ll,ll>ans=tr[l];
  if(l!=r) ans=dodaj(ans, tr[r]);
  while(l/2!=r/2) {
    if(l%2==0) ans=dodaj(ans, tr[l+1]);
    if(r%2==1) ans=dodaj(ans, tr[r-1]);
    l/=2; r/=2;
  }
  return ans;
}
ll cntma(int l, int r) {
  l+=N; r+=N;
  ll ans=max(trma[l], trma[r]);
  while(l/2!=r/2) {
    if(l%2==0) ans=max(ans, trma[l+1]);
    if(r%2==1) ans=max(ans, trma[r-1]);
    l/=2; r/=2;
  }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int n, m;
  cin >> n >> m;
  while(N<=n+3) N*=2;
  A[1]=INF;
  rep(i, n) {
    cin >> A[i+2];
    trma[N+i+1]=A[i+2];
    A[i+2]+=A[i+1];
  }
  rep(i, n) cin >> B[i+1];
  vector<int>S;
  rep(i, n+2) {
    while(S.size() && B[S.back()]>B[i]) S.pop_back();
    if(S.size()) lewo[i]=S.back();
    S.pb(i);
  }
  S.clear();
  for(int i=n+1; i>=0; --i) {
    while(S.size() && B[S.back()]>=B[i]) S.pop_back();
    if(S.size()) prawo[i]=S.back(); else prawo[i]=n-1;
    S.pb(i);
  }
  rep(i, m) {
    cin >> pyt[i].st.st >> pyt[i].st.nd >> pyt[i].nd;
    L[pyt[i].st.st].pb(i);
    R[pyt[i].st.nd-1].pb(i);
  }
  S.clear();
  vector<ll>pref;
  for(int i=n+1; i; --i) {
    while(S.size() && B[S.back()]>=B[i]) {
      S.pop_back();
      pref.pop_back();
    }
    if(S.size()) pref.pb(B[i]*(A[S.back()]-A[i])+pref.back());
    else pref.pb(0);
    S.pb(i);
    for(auto j : L[i]) {
      int po=0, ko=(int)S.size()-1;
      while(po<ko) {
        int sr=(po+ko)/2;
        if(A[S[sr]]<=min(A[i]+pyt[j].nd, A[pyt[j].st.nd])) ko=sr; else po=sr+1;
      }
      wynik[j]+=pref.back()-pref[po];
      wynik[j]+=B[S[po]]*min(min(A[prawo[S[po]]], A[pyt[j].st.nd])-A[S[po]], pyt[j].nd);
      indl[j]=S[po]+1;
    }
  }
  S.clear();
  rep(i, n+1) {
    while(S.size() && B[S.back()]>B[i]) S.pop_back();
    S.pb(i);
    for(auto j : R[i]) {
      int po=0, ko=(int)S.size()-1;
      while(po<ko) {
        int sr=(po+ko)/2;
        if(A[S[sr]]<max(A[pyt[j].st.nd]-pyt[j].nd, A[pyt[j].st.st])) po=sr+1; else ko=sr;
      }
      if(indl[j]<=S[po]) {
        wynik[j]+=B[S[po]]*(A[pyt[j].st.nd]-A[S[po]]);
        wynik[j]+=B[S[po]]*min(A[S[po]]-A[lewo[S[po]]]-pyt[j].nd, 0ll);
      }
      indr[j]=S[po]-1;
    }
  }
  for(int i=1; i<=n; ++i) {
    V.pb({{A[i]-A[lewo[i]], -i}, {(A[i]-A[lewo[i]])*B[i], -B[i]}});
    V.pb({{A[prawo[i]]-A[i], -i}, {(A[prawo[i]]-A[i])*B[i], -B[i]}});
    V.pb({{A[prawo[i]]-A[lewo[i]], -i}, {(A[lewo[i]]-A[prawo[i]])*B[i], B[i]}});
    tr[N+i]={0, B[i]};
  }
  for(int i=N-1; i; --i) {
    tr[i]=dodaj(tr[2*i], tr[2*i+1]);
    trma[i]=max(trma[2*i], trma[2*i+1]);
  }
  rep(i, m) if(indl[i]<=indr[i]) V.pb({{pyt[i].nd, i}, {indl[i], indr[i]}});
  sort(all(V));
  for(auto i : V) {
    if(i.st.nd<0) upd(-i.st.nd, i.nd);
    else {
      pair<ll,ll>x=cnt(i.nd.st, i.nd.nd);
      wynik[i.st.nd]+=x.st+x.nd*i.st.st;
    }
  }
  rep(i, m) if(cntma(pyt[i].st.st, pyt[i].st.nd-1)>pyt[i].nd) wynik[i]=-1;
  rep(i, m) cout << wynik[i] << '\n';
}

• Subtask 1: 11 / 11
• Subtask 2: 14 / 14
• Subtask 3: 31 / 31
• Subtask 4: 44 / 44