Submission #650862

#	Time	Username	Problem	Language	Result	Execution time	Memory
650862		snpmrnhlol	Fire (JOI20_ho_t5)	C++17	7 / 100	1090 ms	160556 KiB

ho_t5

#include <bits/stdc++.h>
using namespace std;
//ifstream fin("a.in");
//ofstream fout("a.out");
typedef long long ll;
ll v[200000],l[200000],r[200000],stv[200000],ans[200000],n;
///i misspled square
ll cnt2 = 0,disp = 300000;
class superfenwick{
    ll fen[550001][2];
private:
    ll query2(ll pos,ll t){
        pos+=disp;
        ll r = 0;
        for(ll i = pos;i > 0;i-=(i&-i))r+=fen[i][t];
        return r;
    }
    void add2(ll pos,ll nr,ll t){
        pos+=disp;
        for(ll i = pos;i <= 550000;i+=(i&-i))fen[i][t]+=nr;
    }
public:
    ll query(ll l,ll r){
        return (query2(r,0)*r - query2(l - 1,0)*(l - 1)) - query2(r,1) + query2(l - 1,1);
    }
    void add(ll l,ll r,ll nr){
        add2(l,nr,0);
        add2(r + 1,-nr,0);
        add2(l,nr*(l - 1),1);
        add2(r + 1,-nr*r,1);
    }
};
superfenwick triangles,squares;
struct events{
    ll tip,t,l,r,nr;
}v2[4000000];
bool cmp(events a,events b){
    if(a.t == b.t)return a.tip < b.tip;
    return a.t < b.t;
}
void addsqaure(ll l,ll r,ll h,ll nr){
    //cout<<"squaredata:"<<l<<','<<r<<','<<h<<','<<nr<<'\n';
    v2[cnt2++] = {0,0,l,r,nr};
    v2[cnt2++] = {0,h,l,r,-nr};
}
void addtriangle(ll l,ll r,ll nr,ll ydisp = 0){
    if(r == n - 1){
        //cout<<"triangledata:"<<l<<','<<r<<','<<nr<<','<<ydisp<<'\n';
        v2[cnt2++] = {1,ydisp,l - ydisp,r - ydisp,nr};
        v2[cnt2++] = {1,r - l + 1 + ydisp,l - ydisp,r - ydisp,-nr};
    }else{
        addtriangle(l,n - 1,nr);
        addtriangle(r + 1,n - 1,-nr,r - l + 1);
        addsqaure(r + 1,n - 1,r - l + 1,-nr);
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll q,i,cnt = 0,j,a,b,c;
    cin>>n>>q;
    for(i = 0;i < n;i++){
        cin>>v[i];
        //v[i] = rand()%1000000000;
    }
    cnt = -1;
    for(i = 0;i < n;i++){
        while(cnt >= 0 && v[i] > v[stv[cnt]]){
            r[stv[cnt--]] = i;
        }
        stv[++cnt] = i;
    }
    while(cnt-- >= 0){
        r[stv[cnt + 1]] = n;
    }
    cnt = -1;
    for(i = n - 1;i >= 0;i--){
        while(cnt >= 0 && v[i] >= v[stv[cnt]]){
            l[stv[cnt--]] = i;
        }
        stv[++cnt] = i;
    }
    while(cnt-- >= 0){
        l[stv[cnt + 1]] = -200005;
    }
    for(i = 0;i < n;i++){
        l[i]++;r[i]--;
        //fout<<"For i = "<<i<<'\n';
        //fout<<l[i]<<' '<<r[i]<<'\n';
        addtriangle(l[i],r[i],v[i]);
        addtriangle(l[i],i - 1,-v[i]);
        addtriangle(i + 1,r[i],-v[i]);
        //cout<<'\n';
    }
    for(i = 0;i < q;i++){
        cin>>a>>b>>c;
        //a = 0;
        //b = 1;
        //c = n;
        v2[cnt2++] = {2,a,b - 1,c - 1,i};
    }
    sort(v2,v2 + cnt2,cmp);
    for(i = 0;i < cnt2;i++){
        if(v2[i].tip == 0){
            squares.add(v2[i].l,v2[i].r,v2[i].nr);
        }else if(v2[i].tip == 1){
            triangles.add(v2[i].l,v2[i].r,v2[i].nr);
        }else{
            ans[v2[i].nr] = squares.query(v2[i].l,v2[i].r) + triangles.query(v2[i].l - v2[i].t,v2[i].r - v2[i].t);
        }
    }
    for(i = 0;i < q;i++)cout<<ans[i]<<'\n';
    return 0;
}

Compilation message (stderr)

ho_t5.cpp: In function 'int main()':
ho_t5.cpp:60:20: warning: unused variable 'j' [-Wunused-variable]
   60 |     ll q,i,cnt = 0,j,a,b,c;
      |                    ^

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