Submission #760864

#	Time	Username	Problem	Language	Result	Execution time	Memory
760864		sysia	Fire (JOI20_ho_t5)	C++17	100 / 100	885 ms	121764 KiB

ho_t5

//Sylwia Sapkowska
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define int long long
typedef pair<int, int> T;
const int oo = 1e18, oo2 = 1e9+7, K = 30;

struct prl{
    //parallelogram 
    int x1, x2, y1, y2, i;
    prl(){}
    prl(int _x1, int _x2, int _y1, int _y2, int _i): x1(_x1), x2(_x2), y1(_y1), y2(_y2), i(_i) {}
};


struct Tree{
    vector<int>tab, lazy;
    int size = 1;
    
    Tree(int n){
        while (size < n) size*=2;
        tab.assign(2*size, 0);
        lazy.assign(2*size, 0);
    }

    void clear(){
        tab.assign(2*size, 0);
        lazy.assign(2*size, 0);
    }

    void update(int x, int lx, int rx, int l, int r, int v){
        if (lx > r || rx < l) return;
        if (lx >= l && rx <= r){
            tab[x] += v * (rx-lx+1);
            lazy[x] += v;
            return;            
        }
        push(x, lx, rx);
        int m = (lx+rx)/2;
        update(2*x, lx, m, l, r, v);
        update(2*x+1, m+1, rx, l, r, v);
        tab[x] = tab[2*x] + tab[2*x+1];
    }

    void push(int x, int lx, int rx){
        if (!lazy[x] || lx == rx) return;
        int m = (rx-lx+1)/2;
        tab[2*x] += lazy[x] * m;
        tab[2*x+1] += lazy[x] * m;
        lazy[2*x] += lazy[x];
        lazy[2*x+1] += lazy[x];
        lazy[x] = 0;  
    }

    int query(int x, int lx, int rx, int l, int r){
        if (lx > r || rx < l) return 0ll;
        if (lx >= l && rx <= r) return tab[x];
        push(x, lx, rx);
        int m = (lx+rx)/2;
        return query(2*x, lx, m, l, r) + query(2*x+1, m+1, rx, l, r);
    }
};
int n;

vector<int>ans, a;
void recsweep(vector<prl>&rec, Tree &t, int sgn){
    int m = (int)rec.size();
    vector<T>ord;
    for (int i = 1; i<=m; i++){
        ord.emplace_back(rec[i-1].y1, -i);
        if (rec[i-1].i >= 0) ord.emplace_back(rec[i-1].y2, i);
    }
    //najpierw odejmujemy stare, pozniej dodajemy, pozniej zapytania
    stable_sort(ord.begin(), ord.end(), [&](auto x, auto y){
        if (x.first != y.first) return x.first < y.first;
        //ten sam x
        T aa = {x.second, rec[abs(x.second)-1].i};
        T b = {y.second, rec[abs(y.second)-1].i};
        if (aa.first >= 0){
            if (b.first >= 0) return aa.second < b.second; //oba poczatki --> chcemy najpierw update
            else return false; //poczatek i koniec --> najpierw poczatek
        } else {
            if (b.first >= 0) return true;
            else return aa.second > b.second; //oba konce
        }
    });
    t.clear();
    for (auto &[smiec, id]: ord){
        if (id < 0){
            id = -id; id--;
            if (rec[id].i < 0){
                ans[-rec[id].i] += sgn*t.query(1, 0, t.size-1, n+rec[id].x1, n+rec[id].x2);
            } else {
                t.update(1, 0, t.size-1, n+rec[id].x1, n+rec[id].x2, a[abs(rec[id].i)]);
            }
        } else {
            id--;
            if (rec[id].i < 0){
                ans[-rec[id].i] += sgn*t.query(1, 0, t.size-1, n+rec[id].x1, n+rec[id].x2);
            } else {
                t.update(1, 0, t.size-1, n+rec[id].x1, n+rec[id].x2, -a[abs(rec[id].i)]);
            }
        }
    }
}

// void parsweep(vector<prl>&a){
//     vector<prl>rectangles;
//     for (auto &[x1, x2, y1, y2, val, i]: a){
//         rectangles.emplace_back(x1-y1, x2-y1, y1, y2, val, i);
//     }
//     recsweep(rectangles);
// }

void solve(){
    int q; cin >> n >> q;
    a.resize(n+1);
    Tree tt(2*n+3);
    for (int i = 1; i<=n; i++) cin >> a[i];
    stack<int>s;
    ans.assign(q+1, 0);
    vector<int>L(n+1, -n);
    for (int i = 1; i<=n; i++){
        while ((int)s.size() && a[s.top()] <= a[i]) s.pop();
        if ((int)s.size()) L[i] = s.top(); 
        s.push(i);
    }
    vector<int>R(n+1, n+1);
    while ((int)s.size()) s.pop();
    for (int i = n; i>=1; i--) {
        while ((int)s.size() && a[s.top()] < a[i]) s.pop();
        if ((int)s.size()) R[i] = s.top(); 
        s.push(i);
    }
    vector<prl>rectangles2, rectangles;
    for (int i = 1; i<=n; i++) {
        // parallelograms.emplace_back(L[i]+1, i, 0, R[i]-L[i]-2, a[i], i);
        rectangles2.emplace_back(L[i]+1, i, 0, R[i]-L[i]-2, i);
        //na prawo
        if (L[i]+1 == i) continue;
        rectangles.emplace_back(R[i], n+2, R[i]-i, R[i]-L[i]-2, i);
        // parallelograms.emplace_back(R[i]+1, n+2, R[i]-i, R[i]-L[i]-2, a[i], i);
        rectangles2.emplace_back(i+1, n+2-R[i]+i, R[i]-i, R[i]-L[i]-2, i);
        //na lewo
        rectangles.emplace_back(-n, i-1, 0, i-L[i]-2, i);
        // parallelograms.emplace_back(-n, L[i], 0, i-L[i]-2, a[i], i);
        rectangles2.emplace_back(-n, L[i], 0, i-L[i]-2, i);

        //x1, x2, y1, y2, val, i ----> x1-y1, x2-y1, y1, y2, val, i;
    }
    for (int i = 1; i<=q; i++){
        int t, l, r; cin >> t >> l >> r;
        rectangles.emplace_back(l, r, t, t, -i);
        // parallelograms.emplace_back(l, r, t, t, 0, -i);
        rectangles2.emplace_back(l-t, r-t, t, t, -i);
    }
    recsweep(rectangles, tt, -1);
    recsweep(rectangles2, tt, 1);
    // parsweep(parallelograms);
    for (int i = 1; i<=q; i++) cout << ans[i] << "\n";
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solve();

    return 0;
}

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