oj.uz

Submission #865930

# Submission time Handle Problem Language Result Execution time Memory
865930 2023-10-25T03:52:28 Z prairie2022 Fire (JOI20_ho_t5) C++17
100 / 100
 603 ms 115644 KB 
#include <bits/stdc++.h>
typedef long long ll;
#define fastio cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
using namespace std;

#define lp pos<<1
#define rp (lp)^1
#define cur (*this)[pos]
#define lc (*this)[lp]
#define rc (*this)[rp]

struct node{
    int l, r, sz = 0;
    ll val = 0, tag = 0;
};

struct TREE: vector<node> {
    void init(int l, int r, int pos){
        cur = {l, r, r-l+1, 0, 0};
        if(cur.sz>1){
            int m = (l+r)>>1;
            init(l, m, lp);
            init(m+1, r, rp);
        }
    }
    inline void push(int pos){
        lc.tag += cur.tag;
        lc.val += cur.tag*lc.sz;
        rc.tag += cur.tag;
        rc.val += cur.tag*rc.sz;
        cur.tag = 0;
    }
    void update(int l, int r, int pos, ll x){
        if(l==cur.l && r==cur.r){
            cur.tag += x;
            cur.val += x*cur.sz;
            return;
        }
        push(pos);
        if(r<rc.l) update(l, r, lp, x);
        else if(l>lc.r) update(l, r, rp, x);
        else update(l, lc.r, lp, x), update(rc.l, r, rp, x);
        cur.val = lc.val + rc.val;
    }
    ll query(int l, int r, int pos){
        if(l==cur.l && r==cur.r) return cur.val;
        push(pos);
        if(r<rc.l) return query(l, r, lp);
        else if(l>lc.r) return query(l, r, rp);
        else return query(l, lc.r, lp)+query(rc.l, r, rp);
    }
} t1, t2; // vertical, diagonal

int n;
inline ll query(int l, int r, int t){
    return t1.query(l, r, 1)+t2.query(n+l-t, n+r-t, 1);
}

int main(){
    fastio
    /*freopen("02-01.txt", "r", stdin);
    freopen("00-test.txt", "w", stdout);*/
    int q;
    cin >> n >> q;
    vector<ll> s(n+1);
    for(int i=1; i<=n; i++) cin >> s[i];
    //building segment tree
    vector<int> l(n+1), r(n+1), stk;
        //nearest larger fire
    for(int i=1; i<=n; i++){
        while(!stk.empty() && s[stk.back()]<s[i]) stk.pop_back();
        l[i] = stk.empty()?-n:stk.back();
        stk.push_back(i);
    }
    stk.clear();
    for(int i=n; i>0; i--){
        while(!stk.empty() && s[stk.back()]<=s[i]) stk.pop_back();
        r[i] = stk.empty()?n+1:stk.back();
        stk.push_back(i);
    }
    /*for(int i=1; i<=n; i++) cout << l[i] << " \n"[i==n];
    for(int i=1; i<=n; i++) cout <<r[i] << " \n"[i==n];*/
    int ed1 = n+1, ed2 = (n<<1)^1;
    t1.resize(ed1<<2), t2.resize(ed2<<2);
    t1.init(1, ed1, 1), t2.init(1, ed2, 1);
    vector<vector<tuple<int, int, ll>>> swp(n+1); //t1+x, t2-x
        //sweeping line
    for(int i=1; i<=n; i++) t1.update(i, ed1, 1, s[i]), t2.update(n+i+1, ed2, 1, -s[i]);
    auto f = [&](int L, int R, ll val){
        L++;
        int t = R-L;
        if(t<=n) swp[t].push_back({R, n+L, val});
    };
    for(int i=1; i<=n; i++){
        f(l[i], r[i], s[i]);
        f(l[i], i, -s[i]);
        f(i, r[i], -s[i]);
    }
    /*for(int i=0; i<=n; i++){
        cout << i << " : ";
        for(const auto &tup: swp[i])
            cout << '{' << get<0>(tup) << ", " << get<1>(tup) << ", " << get<2>(tup) << "} ";
        cout << '\n';
    }
    cout << "s[0] : ";
    for(int i=1; i<=n; i++) cout << query(i, i, 0) << " \n"[i==n];*/
    //processing queries
    vector<ll> ans(q);
    vector<vector<tuple<int, int, int>>> qry(n+1);
    for(int i=0; i<q; i++){
        int T, L, R;
        cin >> T >> L >> R;
        qry[T].push_back({L, R, i});
    }
    for(int i=0; i<=n; i++){
        for(const auto &tup: swp[i]){
            t1.update(get<0>(tup), ed1, 1, get<2>(tup));
            t2.update(get<1>(tup), ed2, 1, -get<2>(tup));
        }
        for(const auto &tup: qry[i])
            ans[get<2>(tup)] = query(get<0>(tup), get<1>(tup), i);
    }
    for(int i=0; i<q; i++) cout << ans[i] << '\n';
    /*fclose(stdin);
    fclose(stdout);*/
    return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 456 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 600 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 1 ms 344 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 1 ms 360 KB Output is correct
32 Correct 1 ms 360 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 543 ms 112588 KB Output is correct
3 Correct 552 ms 110720 KB Output is correct
4 Correct 545 ms 110884 KB Output is correct
5 Correct 545 ms 115128 KB Output is correct
6 Correct 538 ms 113072 KB Output is correct
7 Correct 542 ms 112688 KB Output is correct
8 Correct 540 ms 115644 KB Output is correct
9 Correct 544 ms 114292 KB Output is correct
10 Correct 546 ms 111280 KB Output is correct
11 Correct 546 ms 113248 KB Output is correct
12 Correct 532 ms 110760 KB Output is correct
13 Correct 541 ms 115184 KB Output is correct
14 Correct 546 ms 113440 KB Output is correct
15 Correct 554 ms 115192 KB Output is correct
16 Correct 529 ms 111624 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 486 ms 109612 KB Output is correct
3 Correct 485 ms 107676 KB Output is correct
4 Correct 493 ms 111820 KB Output is correct
5 Correct 480 ms 108456 KB Output is correct
6 Correct 488 ms 109608 KB Output is correct
7 Correct 490 ms 111396 KB Output is correct
8 Correct 485 ms 108584 KB Output is correct
9 Correct 482 ms 108584 KB Output is correct
10 Correct 471 ms 107888 KB Output is correct
11 Correct 497 ms 112800 KB Output is correct
12 Correct 493 ms 112424 KB Output is correct
13 Correct 524 ms 113444 KB Output is correct
14 Correct 489 ms 108588 KB Output is correct
15 Correct 499 ms 112420 KB Output is correct
16 Correct 493 ms 111108 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 569 ms 106936 KB Output is correct
2 Correct 573 ms 108488 KB Output is correct
3 Correct 603 ms 110140 KB Output is correct
4 Correct 588 ms 106128 KB Output is correct
5 Correct 569 ms 106944 KB Output is correct
6 Correct 563 ms 108568 KB Output is correct
7 Correct 588 ms 110192 KB Output is correct
8 Correct 583 ms 108992 KB Output is correct
9 Correct 564 ms 106944 KB Output is correct
10 Correct 597 ms 108988 KB Output is correct
11 Correct 580 ms 107532 KB Output is correct
12 Correct 586 ms 108608 KB Output is correct
13 Correct 562 ms 108340 KB Output is correct
14 Correct 577 ms 107804 KB Output is correct

Subtask #5
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 456 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 600 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 1 ms 344 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 1 ms 360 KB Output is correct
32 Correct 1 ms 360 KB Output is correct
33 Correct 543 ms 112588 KB Output is correct
34 Correct 552 ms 110720 KB Output is correct
35 Correct 545 ms 110884 KB Output is correct
36 Correct 545 ms 115128 KB Output is correct
37 Correct 538 ms 113072 KB Output is correct
38 Correct 542 ms 112688 KB Output is correct
39 Correct 540 ms 115644 KB Output is correct
40 Correct 544 ms 114292 KB Output is correct
41 Correct 546 ms 111280 KB Output is correct
42 Correct 546 ms 113248 KB Output is correct
43 Correct 532 ms 110760 KB Output is correct
44 Correct 541 ms 115184 KB Output is correct
45 Correct 546 ms 113440 KB Output is correct
46 Correct 554 ms 115192 KB Output is correct
47 Correct 529 ms 111624 KB Output is correct
48 Correct 486 ms 109612 KB Output is correct
49 Correct 485 ms 107676 KB Output is correct
50 Correct 493 ms 111820 KB Output is correct
51 Correct 480 ms 108456 KB Output is correct
52 Correct 488 ms 109608 KB Output is correct
53 Correct 490 ms 111396 KB Output is correct
54 Correct 485 ms 108584 KB Output is correct
55 Correct 482 ms 108584 KB Output is correct
56 Correct 471 ms 107888 KB Output is correct
57 Correct 497 ms 112800 KB Output is correct
58 Correct 493 ms 112424 KB Output is correct
59 Correct 524 ms 113444 KB Output is correct
60 Correct 489 ms 108588 KB Output is correct
61 Correct 499 ms 112420 KB Output is correct
62 Correct 493 ms 111108 KB Output is correct
63 Correct 569 ms 106936 KB Output is correct
64 Correct 573 ms 108488 KB Output is correct
65 Correct 603 ms 110140 KB Output is correct
66 Correct 588 ms 106128 KB Output is correct
67 Correct 569 ms 106944 KB Output is correct
68 Correct 563 ms 108568 KB Output is correct
69 Correct 588 ms 110192 KB Output is correct
70 Correct 583 ms 108992 KB Output is correct
71 Correct 564 ms 106944 KB Output is correct
72 Correct 597 ms 108988 KB Output is correct
73 Correct 580 ms 107532 KB Output is correct
74 Correct 586 ms 108608 KB Output is correct
75 Correct 562 ms 108340 KB Output is correct
76 Correct 577 ms 107804 KB Output is correct
77 Correct 585 ms 109828 KB Output is correct
78 Correct 603 ms 111468 KB Output is correct
79 Correct 589 ms 113764 KB Output is correct
80 Correct 584 ms 110496 KB Output is correct
81 Correct 569 ms 109224 KB Output is correct
82 Correct 584 ms 110696 KB Output is correct
83 Correct 592 ms 110632 KB Output is correct
84 Correct 576 ms 108840 KB Output is correct
85 Correct 575 ms 113836 KB Output is correct
86 Correct 574 ms 109124 KB Output is correct
87 Correct 577 ms 113752 KB Output is correct
88 Correct 584 ms 113960 KB Output is correct
89 Correct 562 ms 107984 KB Output is correct
90 Correct 577 ms 111644 KB Output is correct
91 Correct 567 ms 109248 KB Output is correct
92 Correct 557 ms 107800 KB Output is correct
93 Correct 566 ms 110000 KB Output is correct
94 Correct 590 ms 113440 KB Output is correct
95 Correct 577 ms 113452 KB Output is correct
96 Correct 570 ms 109948 KB Output is correct
97 Correct 565 ms 109736 KB Output is correct
98 Correct 576 ms 108280 KB Output is correct
99 Correct 568 ms 110832 KB Output is correct
100 Correct 595 ms 111756 KB Output is correct
101 Correct 555 ms 109528 KB Output is correct
102 Correct 580 ms 112044 KB Output is correct