Submission #701535

#	Time	Username	Problem	Language	Result	Execution time	Memory
701535		jiahng	Fire (JOI20_ho_t5)	C++14	100 / 100	547 ms	70920 KiB

ho_t5

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define int ll
typedef pair<int,int> pi;
typedef vector <int> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define maxn 400010
#define INF (ll)1e9
#define MOD 1000000007
typedef pair <vi, int> pvi;
typedef pair <int,pi> ipi;
typedef vector <pii> vpii;
#define DEBUG 0

int S[maxn];
int N,Q;
int t,l,r;
vpi queries[maxn];
int ans[maxn];

struct FW{
    int fw[maxn],N;
    FW(int _N){
        N = _N;
        FOR(i,1,N) fw[i] = 0;
    }
    void upd(int p,int v){
        assert(p != 0);
        for (int i=p;i<=N;i+=i&(-i)) fw[i] += v;
    }

    int pref_qry(int p){
        int ans = 0;
        for (int i=p;i>0;i-=i&(-i)) ans += fw[i];
        return ans;
    }
    int suff_qry(int p){
        return pref_qry(N) - pref_qry(p-1);
    }
    void print(){
        FOR(i,1,N) cout << pref_qry(i) - pref_qry(i-1) << ' ';
        cout << '\n';
    }

};

int A[maxn],B[maxn],C[maxn],W[maxn];

int32_t main(){
    fast;
    
    // Let an edge a->b be such that a is the greatest index < b such that S[a] >= S[b]
    // Edges are indexed by b
    // Let c be the maximum value of a node in b's subtree
    // Let w be S[a] - S[b]

    cin >> N >> Q;
    FOR(i,1,N) cin >> S[i];
    FW normalfw = FW(N);
    FOR(i,1,N) normalfw.upd(i,S[i]);
    FOR(i,1,Q){
        cin >> t >> l >> r;
        ans[i] += normalfw.pref_qry(r) - normalfw.pref_qry(l-1);
        queries[r].pb({t,i});
        queries[l-1].pb({t,-i});
    }




    FW fixfw_wcb = FW(2*N), fixfw_wab = FW(2*N), fixfw_w = FW(2*N), fixfw_wab2 = FW(2*N), fixfw_w2 = FW(2*N);
    FW stackfw_w = FW(2*N), stackfw_wb = FW(2*N), stackfw_wab = FW(2*N), stackfw_wab2 = FW(2*N), stackfw_w2 = FW(2*N);

    // Fixed fenwicks indexed on c-a
    // Stack fenwicks indexed on a
    //
    // fixfw_wcb stores sum of w(c-b)
    // fixfw_wab stores sum of w(a-b)
    // fixfw_w stores sum of w
    // stackfw_w stores sum of w
    // stackfw_wb stores sum of wb
    // stackfw_wab stores sum of w(a-b)

    stack <int> st;
    int shift = 0;
    FOR(i,1,N){
        while (!st.empty() && S[st.top()] < S[i]){
            int x = st.top();
            if (A[x] != -1){
                stackfw_w.upd(A[x], -W[x]);
                stackfw_wb.upd(A[x], -W[x]*x);
                stackfw_wab.upd(A[x], -W[x]*(A[x]-x));
                stackfw_w2.upd(x-A[x], -W[x]);
                stackfw_wab2.upd(x-A[x], -W[x]*(A[x]-x));

                C[x] += shift; // transfer updates from stack

                fixfw_wcb.upd(C[x] - A[x], W[x]*(C[x]-x));
                fixfw_wab.upd(C[x] - A[x], W[x]*(A[x]-x));
                fixfw_w.upd(C[x] - A[x], W[x]);
                fixfw_w2.upd(x - A[x], W[x]);
                fixfw_wab2.upd(x - A[x], W[x]*(A[x]-x));
            }

            st.pop();
        }


        shift++; // increase all C by 1 in the stack

        if (!st.empty()){
            A[i] = st.top();
            C[i] = i - shift; // have to take into account stack updates
            W[i] = S[A[i]] - S[i];
            
            stackfw_w.upd(A[i], W[i]);
            stackfw_wb.upd(A[i], W[i]*i);
            stackfw_wab.upd(A[i], W[i]*(A[i]-i));
            stackfw_w2.upd(i-A[i], W[i]);
            stackfw_wab2.upd(i-A[i], W[i]*(A[i]-i));
        }else A[i] = -1;
        st.push(i);
        
        if (DEBUG && i == N){
            cout << "FIX\n";

            cout << "wcb "; fixfw_wcb.print();
            cout << "w "; fixfw_w.print();
            cout << "wab "; fixfw_wab.print();
            cout << "w2 "; fixfw_w2.print();
            cout << "wab2 ";  fixfw_wab2.print();
            
            cout << "STACK\n";

            cout << "w "; stackfw_w.print();
            cout << "wb "; stackfw_wb.print();
            cout << "wab "; stackfw_wab.print();
            cout << "w2 "; stackfw_w2.print();
            cout << "wab2 "; stackfw_wab2.print();
        }
        aFOR(q, queries[i]){
            int t = q.f;

            int fix = fixfw_wcb.pref_qry(t) + fixfw_w.suff_qry(t+1)*t + fixfw_wab.suff_qry(t+1) - fixfw_w2.suff_qry(t+1)*t - fixfw_wab2.suff_qry(t+1) + fixfw_w2.pref_qry(t);
            int sta = stackfw_w.suff_qry(i-t) * i - stackfw_wb.suff_qry(i-t) + stackfw_w.pref_qry(i-t-1)*t + stackfw_wab.pref_qry(i-t-1) - stackfw_w2.suff_qry(t+1)*t - stackfw_wab2.suff_qry(t+1) + stackfw_w2.pref_qry(t);
            assert(fix >= 0 && sta >= 0);

            if (q.s < 0) ans[abs(q.s)] -= fix + sta;
            else ans[abs(q.s)] += fix + sta;
        }
    }
    while (!st.empty()){
        C[st.top()] += shift; st.pop(); 
    }
    if (DEBUG) FOR(i,1,N) cout << A[i] << ' ' << C[i] << ' ' << W[i] << '\n';

    FOR(i,1,Q) cout << ans[i] << '\n';

}

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