Submission #1182672

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182672		user736482	Fire (JOI20_ho_t5)	C++20	1 / 100	1083 ms	145304 KiB

ho_t5

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define POT (1<<20)
#define INFL 100000000099

ll n,q,t,a,b,c,k,e,m,h,w,u,pier,ost,cnt;
ll co[200007],co2[200007],ans[200007];
ll sgtree[POT][2],lazy[POT][2];
stack<pair<ll,ll>>st;//co, idx
vector<ll>v;
vector<pair<pair<ll,ll>,pair<ll,ll>>>zap;
vector<pair<pair<ll,ll>,ll>>p3;
vector<pair<pair<ll,ll>,pair<ll,ll>>>p1,p2;//kiedy,co,gdzie

void spych(ll v,ll l,ll r,ll co){
    cnt++;
    sgtree[v*2][co]+=(r-l+1)/2*lazy[v][co];
    sgtree[v*2+1][co]+=(r-l+1)/2*lazy[v][co];
    lazy[v*2][co]+=lazy[v][co];
    lazy[v*2+1][co]+=lazy[v][co];
    lazy[v][co]=0;
}

void add(ll pocz,ll kon, ll l,ll r,ll val,ll v,ll co){
    cnt++;
    if(pocz>r || kon<l)return;
    if(l>=pocz && kon>=r){
        sgtree[v][co]+=(r-l+1)*val;
        lazy[v][co]+=val;
    }
    else{
        spych(v,l,r,co);
        add(pocz,kon,l,(l+r)/2,val,v*2,co);
        add(pocz,kon,(l+r)/2+1,r,val,v*2+1,co);
        sgtree[v][co]=sgtree[v*2][co]+sgtree[v*2+1][co];
    }
}

ll sm(ll pocz,ll kon,ll l,ll r,ll v,ll co){
    cnt++;
    if(pocz>r || kon<l)return 0;
    if(l>=pocz && kon>=r)return sgtree[v][co];
    else{
        spych(v,l,r,co);
     return sm(pocz,kon,l,(l+r)/2,v*2,co)+sm(pocz,kon,(l+r)/2+1,r,v*2+1,co);}
}


int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>q;
    for(ll i=0;i<n;i++){
        cin>>a;
        v.pb(a);
        while(st.size() && st.top().ff<=a){
            co[st.top().ss]=i;
            st.pop();
        }
        st.push({a,i});
    }
    while(st.size()){
        co[st.top().ss]=n;
        st.pop();
    }
    for(ll i=n-1;i>=0;i--){
        a=v[i];
        while(st.size() && st.top().ff<a){
            co2[st.top().ss]=i;
            st.pop();
        }
        st.push({a,i});
    }
    while(st.size()){
        co2[st.top().ss]=-200002;
        st.pop();
    }
    for(ll i=0;i<n;i++){
        p3.pb({{i-1,i-co2[i]-2},-v[i]});
        p3.pb({{co[i]-1,co[i]-i-2},-v[i]});
        p3.pb({{co[i]-1,co[i]-co2[i]-2},v[i]});
    }
    for(auto i : p3){
        
        p1.pb({{0,i.ss},{0,i.ff.ff}});
        p1.pb({{i.ff.ss+1,-i.ss},{0,i.ff.ff}});
        p2.pb({{0,-i.ss},{0,i.ff.ff-1-i.ff.ss}});
        p2.pb({{i.ff.ss+1,i.ss},{0,i.ff.ff-1-i.ff.ss}});
    }
    sort(p1.begin(),p1.end());
    sort(p2.begin(),p2.end());
    reverse(p1.begin(),p1.end());
    reverse(p2.begin(),p2.end());
    for(ll i=0;i<q;i++){
        cin>>a>>b>>c;
        b--;
        c--;
        a=min(a,n-1);
        zap.pb({{a,i},{b,c}});
    }
    sort(zap.begin(),zap.end());
    
    for(auto i : zap){
        if(cnt>100000000){
            cout<<"xd";
            return 0;
        }
        while(p1.size() && i.ff.ff>=p1.back().ff.ff){
            add(1+p1.back().ss.ff,1+p1.back().ss.ss,1,POT/2,p1.back().ff.ss,1,0);
            p1.pop_back();
        }

        while(p2.size() && i.ff.ff>=p2.back().ff.ff){

            add(1,300007+p2.back().ss.ss,1,POT/2,p2.back().ff.ss,1,1);
            p2.pop_back();
        }
        //cout<<sm(1+i.ss.ff,1+i.ss.ss,1,POT/2,1,0)<<" "<<sm(300007-i.ff.ff+i.ss.ff,300007-i.ff.ff+i.ss.ss,1,POT/2,1,1)<<"  ";
        ans[i.ff.ss]=sm(1+i.ss.ff,1+i.ss.ss,1,POT/2,1,0)+sm(300007-i.ff.ff+i.ss.ff,300007-i.ff.ff+i.ss.ss,1,POT/2,1,1);
        
        
    }
    for(ll i=0;i<q;i++)cout<<ans[i]<<"\n";
}

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