Submission #924016

#	Time	Username	Problem	Language	Result	Execution time	Memory
924016		vjudge1	Fire (JOI20_ho_t5)	C++17	100 / 100	959 ms	207088 KiB

ho_t5

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

using namespace std;

#define ll long long
#define ld long double
#define pb push_back
#define pf push_front
#define pii pair<int,int>
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define mem(a,i) memset(a,i,sizeof(a))
#define sz(s) (int)s.size()
#define int ll
#define y1 yy
#define maksim gay
#define ppb pop_back
#define gcd(a,b) __gcd(a,b)
#define in insert

const int dx[4]={-1,0,1,0};
const int dy[4]={0,-1,0,1};

const int inf=1e16;
const int N=5e4+100;
const int MAX=4e5+10;
const int mod=1e9+7;

int n,q;
int a[MAX];
int l[MAX],r[MAX];
int ans[MAX];
vector<pair<pii,int>> zap[MAX];
vector<pair<pii,int>> ev_diag[MAX],ev_norm[MAX];

struct segtree{
  int t[4*MAX];
  int add[4*MAX];
  segtree(){
    mem(t,0);
    mem(add,0);
  }

  void push(int v,int tl,int tr){
    int tm=(tl+tr);
    if(tm>=0)tm/=2;
    else{
      tm=tm/2;
      tm--;
    }
    add[2*v]+=add[v];
    add[2*v+1]+=add[v];
    t[2*v]+=add[v]*(tm-tl+1);
    t[2*v+1]+=add[v]*(tr-tm);
    add[v]=0;
  }

  void update(int v,int tl,int tr,int l,int r,int x){
    // if(v>1000)return;
    if(l>r||tl>r||l>tr)return;
    if(l<=tl&&tr<=r){
      t[v]+=x*(tr-tl+1);
      add[v]+=x;
      return;
    }
    push(v,tl,tr);
    int tm=(tl+tr);
    if(tm>=0)tm/=2;
    else{
      tm=tm/2;
      tm--;
    }
    update(2*v,tl,tm,l,r,x);
    update(2*v+1,tm+1,tr,l,r,x);
    t[v]=t[2*v]+t[2*v+1];
  }

  int get(int v,int tl,int tr,int l,int r){
    if(l>r||tl>r||l>tr)return 0;
    if(l<=tl&&tr<=r)return t[v];
    push(v,tl,tr);
    int tm=(tl+tr);
    if(tm>=0)tm/=2;
    else{
      tm=tm/2;
      tm--;
    }
    return get(2*v,tl,tm,l,r)+get(2*v+1,tm+1,tr,l,r);
  }
}t[2];

void upd_triangle(int lx,int ly,int rx,int ry,int x){
  int lef_diag=lx-ly;
  int rig_diag=rx-ly;
  // cout<<lx<<" "<<rx<<" "<<ly<<" "<<ry<<" "<<x<<" "<<lef_diag<<" "<<rig_diag<<"\n";
  ev_diag[ly].pb({{lef_diag,rig_diag},x});
  ev_diag[ry+1].pb({{lef_diag,rig_diag},-x});
}

void upd_square(int lx,int ly,int rx,int ry,int x){
  // cout<<lx<<" "<<rx<<" "<<ly<<" "<<ry<<" "<<x<<"\n";
  ev_norm[ly].pb({{lx,rx},x});
  ev_norm[ry+1].pb({{lx,rx},-x});
}

void upd_triangle(int l,int r,int x){
  // cout<<l<<" "<<r<<" "<<x<<"\n";
  int h=r-l;
  upd_triangle(l,0,n,n-l,x);
  if(r!=n)upd_triangle(r+1,h+1,n,n-l,-x);
  if(r!=n)upd_square(r+1,0,n,h,-x);
}

void solve(){
  cin>>n>>q;
  stack<int> st;
  for(int i=1;i<=n;i++)cin>>a[i];
  l[1]=0;
  st.push(1);
  for(int i=2;i<=n;i++){
    l[i]=i-1;
    while(!st.empty()&&a[st.top()]<=a[i]){
      l[i]=l[st.top()];
      st.pop();
    }
    st.push(i);
  }
  r[n]=n+1;
  for(int i=n-1;i>=1;i--){
    r[i]=i+1;
    while(!st.empty()&&a[st.top()]<a[i]){
      r[i]=r[st.top()];
      st.pop();
    }
    st.push(i);
  }
  for(int i=1;i<=q;i++){
    int t,l,r;
    cin>>t>>l>>r;
    zap[t].pb({{l,r},i});
  }
  for(int i=1;i<=n;i++){
    if(l[i]==0)l[i]=i-n-1;
    int tl=l[i]+1;
    int tr=r[i]-1;
    if(tl>tr)continue;
    upd_triangle(tl,i-1,-a[i]);
    upd_triangle(i+1,tr,-a[i]);
    upd_triangle(tl,tr,a[i]);
  }
  for(int i=0;i<=n;i++){  
    for(auto x:ev_diag[i]){
      int l=x.F.F,r=x.F.S;
      // cout<<l<<" "<<r<<" "<<x.S<<"\n";
      t[1].update(1,-n,n,l,r,x.S);
    }
    for(auto x:ev_norm[i]){
      int l=x.F.F,r=x.F.S;
      t[0].update(1,0,n,l,r,x.S);
    }
    for(auto x:zap[i]){
      int lef_diag=x.F.F-i;
      int rig_diag=x.F.S-i;
      int lef_norm=x.F.F;
      int rig_norm=x.F.S;
      // cout<<t[1].get(1,-n,n,lef_diag,rig_diag)<<"\n";
      ans[x.S]=t[0].get(1,0,n,lef_norm,rig_norm)+t[1].get(1,-n,n,lef_diag,rig_diag);
    }
  }
  for(int i=1;i<=q;i++){
    cout<<ans[i]<<" ";
  }
}

main(){
  // freopen("prizes.in", "r", stdin);
  // freopen("prizes.out", "w", stdout);
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t=1;
  // cin>>t;
  while(t--){
    solve();
  }
}

Compilation message (stderr)

ho_t5.cpp:179:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  179 | main(){
      | ^~~~

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