oj.uz

Submission #1087274

# Submission time Handle Problem Language Result Execution time Memory
1087274 2024-09-12T12:08:43 Z dwuy Fire (JOI20_ho_t5) C++14
100 / 100
 509 ms 142528 KB 
/**         - dwuy -

　　　　　 ／＞　   フ
　　　　　 | 　_　 _|
　 　　　 ／`ミ _x ノ
　　 　 /　　　 　 |
　　　 /　  ヽ　　 ?
　／￣|　　 |　|　|
　| (￣ヽ＿_ヽ_)_)
　＼二つ

**/
#include <bits/stdc++.h>

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) (int)((s).size())
#define MASK(k)(1LL<<(k))
#define TASK "test"
#define int long long

using namespace std;

typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;

const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MX = 200005;

struct Node{
    int cnts, cntt, sums, sumt, lazy;
    Node() : cnts(0), cntt(0), sums(0), sumt(0), lazy(0) {}
};

struct SMT{
    int n;
    vector<Node> tree;

    SMT(int n = 0){
        this->n = n;
        this->tree.assign(n<<2|3, Node());
    }

    void down(int id){
        if(tree[id].lazy == 0) return;
        int val = tree[id].lazy;
        int ID = id<<1;
        tree[ID].lazy += val;
        tree[ID].cnts += val*tree[ID].cntt;
        tree[ID].sums += val*tree[ID].sumt;
        tree[ID|1].lazy += val;
        tree[ID|1].cnts += val*tree[ID|1].cntt;
        tree[ID|1].sums += val*tree[ID|1].sumt;
        tree[id].lazy = 0;
    }

    Node combine(Node a, Node b){
        Node res;
        res.cntt = a.cntt + b.cntt;
        res.cnts = a.cnts + b.cnts;
        res.sumt = a.sumt + b.sumt;
        res.sums = a.sums + b.sums;
        return res;
    }

    void byebye(int pos){
        int id = 1;
        for(int lo=1, hi=n; lo<hi;){
            int mid = (lo + hi)>>1;
            down(id);
            if(pos <= mid) hi = mid, id = id<<1;
            else lo = mid + 1, id = id<<1|1;
        }
        tree[id] = Node();
        for(id>>=1; id; id>>=1) tree[id] = combine(tree[id<<1], tree[id<<1|1]);
    }

    void update(int pos, int val, int cnt){
        int id = 1;
        for(int lo=1, hi=n; lo<hi;){
            int mid = (lo + hi)>>1;
            down(id);
            if(pos <= mid) hi = mid, id = id<<1;
            else lo = mid + 1, id = id<<1|1;
        }
        tree[id].cntt = 1;
        tree[id].cnts = cnt;
        tree[id].sumt = val;
        tree[id].sums = val*cnt;
        for(id>>=1; id; id>>=1) tree[id] = combine(tree[id<<1], tree[id<<1|1]);
    }

    void query(int f){
        tree[1].lazy += f;
        tree[1].cnts += tree[1].cntt * f;
        tree[1].sums += tree[1].sumt * f;
    }
};

int n, q;
int a[MX];
int pl[MX];
int pr[MX];
int ans[MX];
int T[MX], L[MX], R[MX];
vector<int> G[MX];
vector<int> P0[MX];
vector<int> P1[MX];
vector<int> P2[MX];

void nhap(){
    cin >> n >> q;
    for(int i=1; i<=n; i++) cin >> a[i];
    for(int i=1; i<=q; i++){
        cin >> T[i] >> L[i] >> R[i];
        G[T[i]].push_back(i);
    }
}

void calcPL(){
    stack<int> st;
    for(int i=1; i<=n; i++){
        while(st.size() && a[st.top()] < a[i]) st.pop();
        pl[i] = st.size()? st.top() : -1e9;
        st.push(i);
    }
}

void calcPR(){
    stack<int> st;
    for(int i=n; i>=1; i--){
        while(st.size() && a[st.top()] <= a[i]) st.pop();
        pr[i] = st.size()? st.top() : n + 1;  
        st.push(i);
    }
}

void solve(){  
    calcPL();
    calcPR();
    
    for(int i=1; i<=n; i++){
        P0[min(pr[i] - i, i - pl[i])].push_back(i);
        if(pl[i] > 0){
            P1[max(pr[i] - i, i - pl[i])].push_back(i);
            P2[pr[i] - pl[i]].push_back(i);
        }

    }

    SMT Add(n);
    SMT Keep(n);
    SMT Die(n);

    for(int i=1; i<=n; i++) Add.update(i, a[i], 1);
    for(int t=1; t<=n; t++){
        for(int u: P0[t]){
            Add.byebye(u);
            Keep.update(u, a[u], min(pr[u] - u, u - pl[u]));
        }
        for(int u: P1[t]){
            Keep.byebye(u);
            Die.update(u, a[u], min(pr[u] - u, u - pl[u]));
        }
        for(int u: P2[t]){
            Die.byebye(u);
        }
        Add.query(1);
        Die.query(-1);
        for(int i: G[t]){
            int l = L[i];
            int r = R[i];
            function<int(int)> dwuy = [&](int k) -> int {
                int res = 0;
                int id, lo, hi;
                for(id=1, lo=1, hi=n; lo<hi;){
                    int mid = (lo + hi)>>1;
                    Add.down(id);
                    Die.down(id);
                    int cnt = Add.tree[id<<1].cnts + Die.tree[id<<1].cnts + Keep.tree[id<<1].cnts;
                    if(cnt < k){
                        k -= cnt;
                        res += Add.tree[id<<1].sums + Keep.tree[id<<1].sums + Die.tree[id<<1].sums;
                        id = id<<1|1;
                        lo = mid + 1;
                    }
                    else hi = mid, id = id<<1;
                }
                int cnt = Add.tree[id].cnts + Die.tree[id].cnts + Keep.tree[id].cnts;
                if(cnt < k){
                    k -= cnt;
                    res += Add.tree[id].sums + Keep.tree[id].sums + Die.tree[id].sums;
                    lo++;
                }
                return res + a[lo] * k;
            };
            ans[i] = dwuy(r) - dwuy(l - 1);
        }
    }
    
    for(int i=1; i<=q; i++) cout << ans[i] << '\n';
}

int32_t main(){
    fastIO;
    //file(TASK);

    nhap();
    solve();

    return 0;
}

/*

 20 20
 2 1 2 2 1 1 1 1 2 2 2 1 2 1 1 2 1 2 1 1
 1 1 14
 2 3 18
 4 10 15
 8 2 17
 9 20 20
 4 8 19
 7 2 20
 11 1 5
 13 2 8
 20 1 20
 2 12 15
 7 1 14
 12 7 18
 14 2 17
 9 19 20
 12 12 12
 6 2 15
 11 2 15
 19 12 17
 4 1 20

*/

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19292 KB Output is correct
2 Correct 11 ms 19280 KB Output is correct
3 Correct 8 ms 19292 KB Output is correct
4 Correct 8 ms 19176 KB Output is correct
5 Correct 8 ms 19292 KB Output is correct
6 Correct 8 ms 19280 KB Output is correct
7 Correct 8 ms 19292 KB Output is correct
8 Correct 8 ms 19292 KB Output is correct
9 Correct 8 ms 19388 KB Output is correct
10 Correct 9 ms 19292 KB Output is correct
11 Correct 9 ms 19292 KB Output is correct
12 Correct 9 ms 19292 KB Output is correct
13 Correct 8 ms 19292 KB Output is correct
14 Correct 8 ms 19300 KB Output is correct
15 Correct 9 ms 19288 KB Output is correct
16 Correct 8 ms 19292 KB Output is correct
17 Correct 8 ms 19292 KB Output is correct
18 Correct 8 ms 19292 KB Output is correct
19 Correct 9 ms 19292 KB Output is correct
20 Correct 8 ms 19292 KB Output is correct
21 Correct 9 ms 19292 KB Output is correct
22 Correct 9 ms 19292 KB Output is correct
23 Correct 8 ms 19292 KB Output is correct
24 Correct 8 ms 19292 KB Output is correct
25 Correct 8 ms 19292 KB Output is correct
26 Correct 8 ms 19292 KB Output is correct
27 Correct 9 ms 19244 KB Output is correct
28 Correct 9 ms 19288 KB Output is correct
29 Correct 8 ms 19288 KB Output is correct
30 Correct 8 ms 19412 KB Output is correct
31 Correct 8 ms 19292 KB Output is correct
32 Correct 8 ms 19288 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19292 KB Output is correct
2 Correct 303 ms 137164 KB Output is correct
3 Correct 302 ms 135984 KB Output is correct
4 Correct 296 ms 136668 KB Output is correct
5 Correct 318 ms 140704 KB Output is correct
6 Correct 300 ms 137232 KB Output is correct
7 Correct 300 ms 137592 KB Output is correct
8 Correct 298 ms 141000 KB Output is correct
9 Correct 307 ms 139464 KB Output is correct
10 Correct 299 ms 135364 KB Output is correct
11 Correct 306 ms 139720 KB Output is correct
12 Correct 287 ms 135508 KB Output is correct
13 Correct 308 ms 140232 KB Output is correct
14 Correct 294 ms 140228 KB Output is correct
15 Correct 306 ms 140128 KB Output is correct
16 Correct 297 ms 137144 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19292 KB Output is correct
2 Correct 362 ms 138172 KB Output is correct
3 Correct 340 ms 136272 KB Output is correct
4 Correct 360 ms 142012 KB Output is correct
5 Correct 359 ms 137716 KB Output is correct
6 Correct 371 ms 138852 KB Output is correct
7 Correct 343 ms 139304 KB Output is correct
8 Correct 357 ms 137920 KB Output is correct
9 Correct 367 ms 136948 KB Output is correct
10 Correct 340 ms 135748 KB Output is correct
11 Correct 361 ms 140792 KB Output is correct
12 Correct 344 ms 140696 KB Output is correct
13 Correct 386 ms 140976 KB Output is correct
14 Correct 382 ms 137252 KB Output is correct
15 Correct 378 ms 140736 KB Output is correct
16 Correct 369 ms 140988 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 471 ms 138800 KB Output is correct
2 Correct 477 ms 139532 KB Output is correct
3 Correct 500 ms 142312 KB Output is correct
4 Correct 465 ms 138040 KB Output is correct
5 Correct 462 ms 138716 KB Output is correct
6 Correct 488 ms 139924 KB Output is correct
7 Correct 476 ms 142080 KB Output is correct
8 Correct 492 ms 140600 KB Output is correct
9 Correct 504 ms 138876 KB Output is correct
10 Correct 509 ms 140884 KB Output is correct
11 Correct 495 ms 139344 KB Output is correct
12 Correct 479 ms 139984 KB Output is correct
13 Correct 478 ms 139412 KB Output is correct
14 Correct 477 ms 139692 KB Output is correct

Subtask #5
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19292 KB Output is correct
2 Correct 11 ms 19280 KB Output is correct
3 Correct 8 ms 19292 KB Output is correct
4 Correct 8 ms 19176 KB Output is correct
5 Correct 8 ms 19292 KB Output is correct
6 Correct 8 ms 19280 KB Output is correct
7 Correct 8 ms 19292 KB Output is correct
8 Correct 8 ms 19292 KB Output is correct
9 Correct 8 ms 19388 KB Output is correct
10 Correct 9 ms 19292 KB Output is correct
11 Correct 9 ms 19292 KB Output is correct
12 Correct 9 ms 19292 KB Output is correct
13 Correct 8 ms 19292 KB Output is correct
14 Correct 8 ms 19300 KB Output is correct
15 Correct 9 ms 19288 KB Output is correct
16 Correct 8 ms 19292 KB Output is correct
17 Correct 8 ms 19292 KB Output is correct
18 Correct 8 ms 19292 KB Output is correct
19 Correct 9 ms 19292 KB Output is correct
20 Correct 8 ms 19292 KB Output is correct
21 Correct 9 ms 19292 KB Output is correct
22 Correct 9 ms 19292 KB Output is correct
23 Correct 8 ms 19292 KB Output is correct
24 Correct 8 ms 19292 KB Output is correct
25 Correct 8 ms 19292 KB Output is correct
26 Correct 8 ms 19292 KB Output is correct
27 Correct 9 ms 19244 KB Output is correct
28 Correct 9 ms 19288 KB Output is correct
29 Correct 8 ms 19288 KB Output is correct
30 Correct 8 ms 19412 KB Output is correct
31 Correct 8 ms 19292 KB Output is correct
32 Correct 8 ms 19288 KB Output is correct
33 Correct 303 ms 137164 KB Output is correct
34 Correct 302 ms 135984 KB Output is correct
35 Correct 296 ms 136668 KB Output is correct
36 Correct 318 ms 140704 KB Output is correct
37 Correct 300 ms 137232 KB Output is correct
38 Correct 300 ms 137592 KB Output is correct
39 Correct 298 ms 141000 KB Output is correct
40 Correct 307 ms 139464 KB Output is correct
41 Correct 299 ms 135364 KB Output is correct
42 Correct 306 ms 139720 KB Output is correct
43 Correct 287 ms 135508 KB Output is correct
44 Correct 308 ms 140232 KB Output is correct
45 Correct 294 ms 140228 KB Output is correct
46 Correct 306 ms 140128 KB Output is correct
47 Correct 297 ms 137144 KB Output is correct
48 Correct 362 ms 138172 KB Output is correct
49 Correct 340 ms 136272 KB Output is correct
50 Correct 360 ms 142012 KB Output is correct
51 Correct 359 ms 137716 KB Output is correct
52 Correct 371 ms 138852 KB Output is correct
53 Correct 343 ms 139304 KB Output is correct
54 Correct 357 ms 137920 KB Output is correct
55 Correct 367 ms 136948 KB Output is correct
56 Correct 340 ms 135748 KB Output is correct
57 Correct 361 ms 140792 KB Output is correct
58 Correct 344 ms 140696 KB Output is correct
59 Correct 386 ms 140976 KB Output is correct
60 Correct 382 ms 137252 KB Output is correct
61 Correct 378 ms 140736 KB Output is correct
62 Correct 369 ms 140988 KB Output is correct
63 Correct 471 ms 138800 KB Output is correct
64 Correct 477 ms 139532 KB Output is correct
65 Correct 500 ms 142312 KB Output is correct
66 Correct 465 ms 138040 KB Output is correct
67 Correct 462 ms 138716 KB Output is correct
68 Correct 488 ms 139924 KB Output is correct
69 Correct 476 ms 142080 KB Output is correct
70 Correct 492 ms 140600 KB Output is correct
71 Correct 504 ms 138876 KB Output is correct
72 Correct 509 ms 140884 KB Output is correct
73 Correct 495 ms 139344 KB Output is correct
74 Correct 479 ms 139984 KB Output is correct
75 Correct 478 ms 139412 KB Output is correct
76 Correct 477 ms 139692 KB Output is correct
77 Correct 379 ms 138820 KB Output is correct
78 Correct 368 ms 140332 KB Output is correct
79 Correct 381 ms 142528 KB Output is correct
80 Correct 365 ms 138428 KB Output is correct
81 Correct 364 ms 138208 KB Output is correct
82 Correct 362 ms 140212 KB Output is correct
83 Correct 387 ms 139592 KB Output is correct
84 Correct 381 ms 137492 KB Output is correct
85 Correct 360 ms 141176 KB Output is correct
86 Correct 368 ms 138296 KB Output is correct
87 Correct 337 ms 140992 KB Output is correct
88 Correct 368 ms 140244 KB Output is correct
89 Correct 324 ms 136132 KB Output is correct
90 Correct 334 ms 139392 KB Output is correct
91 Correct 329 ms 137272 KB Output is correct
92 Correct 317 ms 135788 KB Output is correct
93 Correct 326 ms 138304 KB Output is correct
94 Correct 331 ms 141904 KB Output is correct
95 Correct 327 ms 140168 KB Output is correct
96 Correct 323 ms 138032 KB Output is correct
97 Correct 348 ms 137904 KB Output is correct
98 Correct 370 ms 136384 KB Output is correct
99 Correct 375 ms 138436 KB Output is correct
100 Correct 374 ms 138764 KB Output is correct
101 Correct 380 ms 137272 KB Output is correct
102 Correct 381 ms 139616 KB Output is correct