Submission #1024621

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024621		manizare	Fire (JOI20_ho_t5)	C++14	100 / 100	224 ms	118600 KiB

ho_t5

#include <bits/stdc++.h>
 
 
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define ld long double 
#define int long long
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= b;i++)
#define per(i, a , b) for(int i=a;i >= b;i--)
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 6e5 + 10  , sq = 550,  inf = 1e18+10 , mod = 10007 , lg = 20  ;
int a[maxn] , n , q ;

struct fen{
    int f1[maxn] , f2[maxn] ; 
    void upd(int id ,int x ,int y ){
        id += n+1 ; 
        while(id <= 2*n+q+1){
            f1[id] += x*y ;
            f2[id] += y ; 
            id += id&-id; 
        }
    }
    int que(int x ,int w){
        int s1 =0 , s2 =0 ;
        x += n+1 ;
        while(x){
            s1 += f1[x] ; 
            s2 += f2[x] ; 
            x -= x&-x ;
        }
        return s2*w - s1 ;   
    }   
    int bz(int l , int r , int x){
        return (que(r, x) - que(l-1 , x)) ;
    }
};
fen f1 , f2 , f3 ;  
int d1[maxn] , d2[maxn] , ans[maxn]  ; 
vector <int> u1[maxn];
vector <pii>  up[maxn] ;
vector <pair<pii,int> >  q1[maxn] ; 

void add(int x , int w  ,int t){
    up[t].pb({x,w}) ;
}

void c1(){
    vector <int> vec ; 
    rep(i ,1 ,n){
        while(sz(vec) && a[vec.back()] <= a[i])vec.pop_back() ;
        if(sz(vec) == 0)d1[i] = 0 ;
        else d1[i] = vec.back() ; 
        vec.pb(i) ; 
    }
    vec.clear() ; 
    per(i , n , 1){
        while(sz(vec) && a[vec.back()] < a[i])vec.pop_back() ;
        if(sz(vec) == 0)d2[i] = n+1 ;
        else d2[i] = vec.back() ; 
        vec.pb(i) ; 
    }   
    rep(i ,1 ,n)u1[d1[i]].pb(i) ;
    rep(i ,1 ,n){
        vector <pii> f; 
        f.pb({i,a[i]}) ; 
        for(int x : u1[i]){
            f.pb({x , a[i]-a[x]}) ; 
        }
        f.pb({d2[i] , 0}) ;
        rep(j , 0, sz(f)-2){
            int ti = f[j].F - i ; 
            add(f[j].F, f[j].S , ti);
            add(f[j+1].F , -f[j].S , ti+f[j+1].F-f[j].F) ;   
        }
    }
}

void upd(int x ,int w , int ti){
    if(x==n+1)return ; 
    f1.upd(x , ti , w) ;
    f2.upd(ti-x+1 , ti-x+1 ,w) ;
    f3.upd(x , ti-x+1 , w) ;
}
int sl(int x , int ti){
    int ans = 0 ;
    ans += f1.bz(1 , x , ti);
    ans -= f2.bz(-n , ti-x , ti-x) ;
    ans += f3.bz(x+1 , n , ti-x) ; 
    return ans ; 
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);    
    cin >> n >> q; 
    rep(i , 1, n){
        cin >> a[i] ; 
    }   
    c1() ;
    rep(i ,1 ,q){
        int l,  r , ti ;
        cin >> ti >> l >> r ;
        q1[ti].pb({{l,r} , i}) ; 
    }
    rep(i , 0, n){
        for(auto [x,w] : up[i]){
            upd(x , w , i-1) ;
        }
        for(auto [b,j] : q1[i]){
            ans[j] += sl(b.S,i) ;
            ans[j] -= sl(b.F-1 ,i) ; 
        }   
    }
    rep(i ,1 , q){
        cout << ans[i] << "\n" ; 
    }   
}
/*
*/

Compilation message (stderr)

ho_t5.cpp: In function 'int main()':
ho_t5.cpp:113:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  113 |         for(auto [x,w] : up[i]){
      |                  ^
ho_t5.cpp:116:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  116 |         for(auto [b,j] : q1[i]){
      |                  ^

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