Submission #207077

#	Time	Username	Problem	Language	Result	Execution time	Memory
207077		Saboon	Fire (JOI20_ho_t5)	C++14	8 / 100	1016 ms	96384 KiB

ho_t5

#include<bits/stdc++.h> 
using namespace std; 
  
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") 
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") 
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) 
#define F first 
#define S second 
#define int long long 
const int maxn = 2e5 + 12; 
vector <pair <pair <int, int>, pair <pair <int, int> , int> > > Q; 
int n, q; 
int L[maxn], R[maxn]; 
int LQ[maxn], RQ[maxn], TQ[maxn]; 
int ans[maxn], seg[16 * maxn], lazy[16 * maxn], a[maxn]; 
  
inline void shift(int id, int l, int r) { 
    if(lazy[id] == 0) return; 
    int val = lazy[id]; 
    lazy[id] = 0; 
    int mid = (l + r) >> 1; 
    if(l == r - 1) return; 
    seg[id * 2 + 0] += (mid - l) * val; 
    seg[id * 2 + 1] += (r - mid) * val; 
    lazy[id * 2 + 0] += val; 
    lazy[id * 2 + 1] += val; 
    return; 
} 
  
inline void add(int id, int l, int r, int st, int en, int val) { 
    //shift(id, l, r); 
    if(en <= l || r <= st) return; 
    if(st <= l && r <= en) { 
        seg[id] += (r - l) * val; 
        lazy[id] += val; 
        return; 
    } 
    int mid = (l + r) >> 1; 
    shift(id, l, r); 
    add(id * 2 + 0, l, mid, st, en, val); 
    add(id * 2 + 1, mid, r, st, en, val); 
    seg[id] = seg[id * 2 + 0] + seg[id * 2 + 1]; 
    return; 
} 
  
inline int get(int id, int l, int r, int st, int en) { 
    if(en <= l || r <= st) return 0; 
    if(st <= l && r <= en) return seg[id]; 
    shift(id, l, r); 
    int mid = (l + r) >> 1; 
    return get(id * 2 + 0, l, mid, st, en) + 
           get(id * 2 + 1, mid, r, st, en); 
} 
  
//type, time, l, r, val 
//FF FS SFF SFS SS 
bool cmp(pair <pair <int, int>, pair <pair <int, int> , int> > a, pair <pair <int, int>, pair <pair <int, int> , int> > b) { 
    if(a.F.S != b.F.S) return a.F.S < b.F.S; 
    return a.F.F < b.F.F; 
} 
  
int32_t main() { 
    IOS; 
    cin >> n >> q; 
    for (int i = 0; i < n; i++) cin >> a[i]; 
    for (int i = 0; i < q; i++) cin >> TQ[i] >> LQ[i] >> RQ[i], LQ[i]--; 
    vector <pair <int, int> > V; 
    V.push_back({1e9, -maxn + 1}); 
    for (int i = 0; i < n; i++) { 
        while(V.back().F < a[i]) V.pop_back(); 
        L[i] = V.back().S; 
        V.push_back({a[i], i}); 
    } 
    V.clear(); 
    V.push_back({1e9, n}); 
    for (int i = n - 1; i >= 0; i--) { 
        while(V.back().F <= a[i]) V.pop_back(); 
        R[i] = V.back().S; 
        V.push_back({a[i], i}); 
    } 
    V.clear(); 
    for (int i = 0; i < n; i++) { 
        //id, l, r, st, en, val 
        add(1, -maxn, maxn, i + 1, maxn, -a[i]); 
        //type, time,  l,   r,  val 
        //FF     FS    SFF SFS  SS 
        Q.push_back({{0, R[i] - L[i] - 1}, {{L[i] + 1, maxn}, -a[i]}}); 
        Q.push_back({{0, i - L[i]}, {{L[i] + 1, maxn}, a[i]}}); 
        Q.push_back({{0, R[i] - i - 1}, {{i + 1, maxn}, a[i]}}); 
    } 
    for (int i = 0; i < q; i++) { 
        Q.push_back({{1,TQ[i]}, {{LQ[i] - TQ[i], RQ[i] - TQ[i]}, i}}); 
    } 
    sort(Q.begin(), Q.end(), cmp); 
    for (auto x : Q) { 
        if(x.F.F == 1) { 
            ans[x.S.S] += get(1, -maxn + 1, maxn, x.S.F.F, x.S.F.S); 
            continue; 
        } 
        add(1, -maxn + 1, maxn, x.S.F.F, x.S.F.S, x.S.S); 
    } 
    Q.clear(); 
    for (int i = 0; i < 16 * maxn; i++) seg[i] = 0, lazy[i] = 0; 
    for (int i = 0; i < n; i++) { 
        add(1, -maxn + 1, maxn, i, maxn, a[i]); 
        Q.push_back({{0, i - L[i]}, {{i, maxn}, -a[i]}}); 
        Q.push_back({{0, R[i] - i - 1}, {{R[i], maxn}, -a[i]}}); 
        Q.push_back({{0, R[i] - L[i] - 1}, {{R[i], maxn}, a[i]}}); 
    } 
    for (int i = 0; i < q; i++) { 
        Q.push_back({{1,TQ[i]}, {{LQ[i], RQ[i]}, i}}); 
    } 
    sort(Q.begin(), Q.end(), cmp); 
    for (auto x : Q) { 
        if(x.F.F == 1) { 
            ans[x.S.S] += get(1, -maxn + 1, maxn, x.S.F.F, x.S.F.S); 
            continue; 
        } 
        add(1, -maxn + 1, maxn, x.S.F.F, x.S.F.S, x.S.S); 
    } 
    for (int i = 0; i < q; i++) cout << ans[i] << '\n'; 
    return 0; 
} 

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