제출 #501646

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
501646		balbit	Fire (JOI20_ho_t5)	C++14	100 / 100	874 ms	115288 KiB

ho_t5

#include <bits/stdc++.h>
#define int ll
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<ll, ll>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;


void GG(){cout<<"0\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b,mo) % mo;
}


const int maxn = 4e5+10;
struct act{
    int l, v;
};
struct seg{
    ll s[maxn*4], tg[maxn*4];
    void push(int o, int l, int r){
        if (tg[o]) {
            s[o] += tg[o] * (r-l+1);
            if (l!=r) {
                tg[o*2] += tg[o];
                tg[o*2+1] += tg[o];
            }
            tg[o] = 0;
        }
    }
    void MO(int L, int R, ll v, int o=1, int l=0, int r=maxn-1) {
        push(o,l,r);
        if (l>R || r<L) return;
        if (l >= L && r <= R) {
            tg[o] += v;
            push(o,l,r);
            return;
        }
        int mid = (l+r)/2;
        MO(L,R,v,o*2,l,mid);
        MO(L,R,v,o*2+1,mid+1,r);
        s[o] = (s[o*2]+ s[o*2+1]);
    }

    ll QU(int L, int R, int o=1, int l=0, int r=maxn-1) {
        push(o,l,r);
        if (l>R || r<L) return 0;
        if (l>=L && r<=R) {
            return s[o];
        }
        int mid = (l+r)/2;
        return (QU(L,R,o*2,l,mid)+ QU(L,R,o*2+1,mid+1,r));
    }

    void go(act A) {
        MO(max(A.l,0ll), maxn-1, A.v);
    }

    seg(){
        memset(s, 0, sizeof s);
        memset(tg, 0, sizeof tg);
    }
};

seg straight, slant;



vector<act> straighta[maxn], slanta[maxn];

void Tri(int a, int b, int v) {
    if (v == 0) return;
    bug("tri", a, b, v);

    int steps = b-a+1;
    straight.MO(b+1, maxn-1, -v);
    slant.MO(a, maxn-1, v);

    if (steps < maxn) {
        straighta[steps].pb({b+1, +v});
        slanta[steps].pb({a, -v});
    }
}

int lbig[maxn], rbig[maxn];
int a[maxn];

ll ask(int t, int l, int r) {
    ll str = straight.QU(l,r);
    ll sla = slant.QU(max(l-t,0ll), max(r-t,0ll));
    return str + sla;
}

ll ans[maxn];

struct que{
    int t, l, r, id;
};

signed main(){
    IOS();
    bug(1,2);
    int n; cin>>n;
    int q; cin>>q;
    REP(i,n) {
        cin>>a[i];
    }

    {
        vector<pii> yo; yo.pb({-n-2,inf}); // stuff on the left are bigger
        REP(i,n) {
            while (yo.back().s < a[i]) {
                yo.pop_back();
            }
            lbig[i] = yo.back().f;
            yo.pb({i, a[i]});
            bug(i, lbig[i]);
        }
    }

    {
        vector<pii> yo; yo.pb({n,inf}); // stuff on the left are bigger
        RREP(i,n) {
            while (yo.back().s <= a[i]) { // leq here
                yo.pop_back();
            }
            rbig[i] = yo.back().f;
            yo.pb({i, a[i]});
            bug(i, rbig[i]);
        }
    }

    REP(i,n) {
        int prv = lbig[i] + 1;
        int j = rbig[i] - 1;
        Tri(prv, j, a[i]);
        Tri(prv, i-1, -a[i]);
        Tri(i+1, j, -a[i]);
    }

    vector<que> bar;

    REP(i,q) {
        int t,l,r;
        cin>>t>>l>>r;
        --l; --r;
        bar.pb({t,l,r,i});
    }

    sort(ALL(bar), [&](que a, que b){return a.t < b.t;});

    int nat = -1;

    for (auto e : bar) {
        while (nat < e.t) {
            ++nat;
            bug(nat);
            for (act a : straighta[nat]) {
                bug("straight", a.l, a.v);
                straight.go(a);
            }
            for (act a : slanta[nat]) {
                bug(a.l, a.v);
                slant.go(a);
            }
        }

        ans[e.id] = ask(e.t, e.l, e.r);

    }

    REP(i,q) {
        cout<<ans[i]<<endl;
    }



}

/*
5 3
5 0 0 0 0
0 1 3
1 1 3
2 1 3
*/

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