제출 #1287996

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1287996		nguyn	Fire (JOI20_ho_t5)	C++20	100 / 100	378 ms	149240 KiB

ho_t5

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

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif // LOCAL

#define ll long long 
#define F first
#define S second
#define pb push_back
#define pii pair<int, int>

const int N = 2e5 + 5;
const ll inf = 1e18; 

struct BIT {
    int n; 
    ll bit[2 * N + 1]; 

    BIT() {}
    BIT(int n) : n(n) {}

    void update(int id, ll val) {
        id += N; 
        for (int i = id; i <= n; i += (i & -i)) bit[i] += val; 
    }

    ll get(int id) {
        ll res = 0;
        id += N; 
        for (int i = id; i > 0; i -= (i & -i)) res += bit[i];
        return res; 
    }

} bit1(2 * N), bit2(2 * N), bit3(2 * N), bit4(2 * N), bit5(2 * N);

struct Query {
    int l, r, id; 
};

vector<Query> que[N]; 
vector<pair<int, ll>> ev1[2 * N], ev2[2 * N], ev3[2 * N], ev4[2 * N], ev5[2 * N]; 
int n, q;
ll res[N]; 
int a[N], l[N], r[N]; 
vector<int> vec;

ll cal(int t, int r) {
    return 1ll * (r - t) * (bit1.get(r - t) + bit2.get(r)) + (bit3.get(r - t) + bit4.get(r)) + 1ll * t * bit5.get(r); 
}

void add_tri(int l, int r, int val) {
    ev1[0].pb({l, val});
    ev2[0].pb({r + 1, - val});
    ev3[0].pb({l, -1ll * val * (l - 1)}); 
    ev4[0].pb({r + 1, 1ll * val * r}); 
    ev5[0].pb({r + 1, - val});
    ev1[r - l + 1].pb({l, - val});
    ev2[r - l + 1].pb({r + 1, val});
    ev3[r - l + 1].pb({l, 1ll * val * (l - 1)}); 
    ev4[r - l + 1].pb({r + 1, - 1ll * val * r}); 
    ev5[r - l + 1].pb({r + 1, val}); 
} 

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i]; 
    }
    for (int i = 1; i <= q; i++) {
        int t, u, v;
        cin >> t >> u >> v;
        que[t].pb({u, v, i}); 
    }
    for (int i = 1; i <= n; i++) {
        while(!vec.empty() && a[i] >= a[vec.back()]) vec.pop_back(); 
        if (vec.empty()) l[i] = - n - 2; 
        else l[i] = vec.back(); 
        vec.pb(i); 
    }    
    vec.clear();
    for (int i = n; i >= 1; i--) {
        while(!vec.empty() && a[i] > a[vec.back()]) vec.pop_back(); 
        if (vec.empty()) r[i] = n + 2;
        else r[i] = vec.back();  
        vec.pb(i); 
    }
    for (int i = 1; i <= n; i++) {
        add_tri(l[i] + 1, r[i] - 1, a[i]); 
        add_tri(l[i] + 1, i - 1, - a[i]); 
        add_tri(i + 1, r[i] - 1, - a[i]); 
    }
    for (int i = 0; i <= n; i++) {
        for (auto it : ev1[i]) bit1.update(it.F, it.S);
        for (auto it : ev2[i]) bit2.update(it.F, it.S);  
        for (auto it : ev3[i]) bit3.update(it.F, it.S);  
        for (auto it : ev4[i]) bit4.update(it.F, it.S);  
        for (auto it : ev5[i]) bit5.update(it.F, it.S);  
        for (auto it : que[i]) {
            res[it.id] = cal(i, it.r) - cal(i, it.l - 1); 
        }
    }
    for (int i = 1; i <= q; i++) {
        cout << res[i] << '\n'; 
    }
}

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