Submission #256446

#	Time	Username	Problem	Language	Result	Execution time	Memory
256446		doowey	Fire (JOI20_ho_t5)	C++14	0 / 100	303 ms	45688 KiB

ho_t5

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)2e5 + 10;

int m;
int A[N];
int L[N];
int R[N];

const int M = (int)1e6 + 100;
ll tree[M];

void innit(){
    for(int i = 0 ; i < M; i ++ ){
        tree[i] = 0;
    }
}

void upd(int id, ll v){
    id += m;
    tree[id] += v;
    id /= 2;
    while(id > 0){
        tree[id] = tree[id * 2] + tree[id * 2 + 1];
        id /= 2;
    }
}

ll qry(int l, int r){
    l += m;
    r += m;
    ll res = 0;
    while(l <= r){
        if(l % 2 == 1) res += tree[l ++ ];
        if(r % 2 == 0) res += tree[r -- ];
        l /= 2;
        r /= 2;
    }
    return res;
}

struct Q{
    int lef;
    int rig;
    int idx;
};

vector<Q> typ[N];
ll ans[N];
vector<Q> eve[N];
vector<pii> lin[N];

int main(){
    fastIO;
    int n, q;
    cin >> n >> q;
    m = n * 2 + 10;
    for(int i = 1; i <= n; i ++ ){
        cin >> A[i];
    }
    int tt, li, ri;
    for(int qq = 0; qq < q; qq ++ ){
        cin >> tt >> li >> ri;
        typ[tt].push_back({li, ri, qq});
    }
    vector<int> id;
    for(int i = 1; i <= n; i ++ ){
        while(!id.empty() && A[id.back()] <= A[i]){
            R[id.back()] = i;
            id.pop_back();
        }
        if(id.empty()){
            L[i] = i-n;
        }
        else{
            L[i] = id.back();
        }
        id.push_back(i);
    }
    for(int i = 1; i <= n; i ++ ){
        if(R[i] == 0)
            R[i] = i+n;
    }
    int len;
    for(int i = 1; i <= n; i ++ ){
        if(i - L[i] < R[i] - i){
            len = R[i] - i;
            for(int j = 0; j < i - L[i]; j ++ ){
                eve[j].push_back({i, j, A[i]});
                if(j + len <= n)
                    eve[j + len].push_back({i + len, j + len, -A[i]});
            }
        }
        else{
            len = i - L[i];
            for(int j = 0 ; j < R[i] - i; j ++){
                lin[j].push_back(mp(i + j, A[i]));
                if(j + len <= n)
                    lin[j + len].push_back(mp(i + j, -A[i]));
            }
        }
    }
    innit();
    for(int t = 0; t <= n; t ++ ){
        for(auto q : eve[t]){
            upd(q.lef - t + n, q.idx);
        }
        for(auto q : typ[t]){
            ans[q.idx] += qry(q.lef - t + n, q.rig - t + n);
        }
    }
    innit();
    for(int t = 0; t <= n; t ++ ){
        for(auto q : lin[t]){
            upd(q.fi, q.se);
        }
        for(auto q : typ[t]){
            ans[q.idx] += qry(q.lef, q.rig);
        }
    }
    for(int t =0 ; t < q ;t ++ )
        cout << ans[t] << "\n";
    return 0;
}

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