oj.uz

답안 #540867

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
540867 2022-03-21T21:31:14 Z AlperenT Izbori (COCI22_izbori) C++17
110 / 110
 630 ms 45604 KB 
#include <bits/stdc++.h>

using namespace std;

const int FIXNEG = 2e5 + 5, N = FIXNEG * 2;

struct SegTree{
    pair<int, long long> tree[N * 4];
    int ladd[N * 4];
    bool lset[N * 4];

    pair<int, long long> merge(pair<int, long long> a, pair<int, long long> b, long long cnt){
        cnt = max(cnt, 0ll);

        pair<int, long long> c;

        c.first = a.first + b.first;
        c.second = a.second + cnt * a.first + b.second;

        return c;
    }

    void push(int v, int l, int r){
        if(lset[v]){
            tree[v] = {0, 0};

            if(v * 2 < N * 4){
                lset[v * 2] = lset[v * 2 + 1] = true;
                ladd[v * 2] = ladd[v * 2 + 1] = 0;
            }

            lset[v] = 0;
        }
        if(ladd[v]){
            tree[v].first += ladd[v] * (r - l + 1);
            tree[v].second += ladd[v] * (((r - l + 1ll) * (r - l + 2ll)) / 2);

            if(v * 2 < N * 4){
                ladd[v * 2] += ladd[v], ladd[v * 2 + 1] += ladd[v];
            }

            ladd[v] = 0;
        }
    }

    void reset(){
        lset[1] = true, ladd[1] = 0;
    }

    pair<int, long long> query(int l, int r, int v = 1, int tl = 0, int tr = N - 1){
        if(l > r) return {0, 0};
        else{
            push(v, tl, tr);

            if(l == tl && r == tr) return tree[v];
            else{
                int tm = tl + (tr - tl) / 2;

                return merge(query(l, min(tm, r), v * 2, tl, tm), query(max(tm + 1, l), r, v * 2 + 1, tm + 1, tr), r - max(tm + 1, l) + 1);
            }
        }
    }

    void rangeadd(int l, int r, int v = 1, int tl = 0, int tr = N - 1){
        if(l > r) return;
        else{
            push(v, tl, tr);

            if(l == tl && r == tr) ladd[v] += 1, push(v, tl, tr);
            else{
                int tm = tl + (tr - tl) / 2;

                rangeadd(l, min(tm, r), v * 2, tl, tm);
                rangeadd(max(tm + 1, l), r, v * 2 + 1, tm + 1, tr);

                push(v * 2, tl, tm), push(v * 2 + 1, tm + 1, tr);

                tree[v] = merge(tree[v * 2], tree[v * 2 + 1], tr - (tm + 1) + 1);
            }
        }
    }
};

SegTree sgt;

int n, arr[N], prvindx, prvans;
long long ans;

map<int, vector<int>> mp;

vector<int> v;

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);

    cin >> n;

    for(int i = 1; i <= n; i++){
        cin >> arr[i];

        mp[arr[i]].push_back(i);
    }

    for(auto p : mp){
        v = p.second;

        prvindx = 0, prvans = 0 + FIXNEG;

        sgt.reset();
        sgt.rangeadd(0 + FIXNEG, 0 + FIXNEG);

        for(auto indx : v){
            ans += sgt.query(prvans - (indx - prvindx - 1) - 1, prvans - 2).second + sgt.query(0, prvans - (indx - prvindx - 1) - 2).first * (long long)(indx - prvindx - 1);

            sgt.rangeadd(prvans - (indx - prvindx - 1), prvans - 1);

            prvans = prvans - (indx - prvindx - 1) + 1;

            ans += sgt.query(0, prvans - 1).first;

            sgt.rangeadd(prvans, prvans);

            prvindx = indx;
        }

        prvans = prvans - (n - prvindx);

        ans += sgt.query(prvans - 1, prvans - 1 + (n - prvindx) - 1).second + sgt.query(0, prvans - 2).first * (long long)(n - prvindx);
    }

    cout << ans;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 25376 KB Output is correct
2 Correct 13 ms 25376 KB Output is correct
3 Correct 12 ms 25452 KB Output is correct
4 Correct 12 ms 25408 KB Output is correct
5 Correct 13 ms 25436 KB Output is correct
6 Correct 13 ms 25504 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 25376 KB Output is correct
2 Correct 13 ms 25376 KB Output is correct
3 Correct 12 ms 25452 KB Output is correct
4 Correct 12 ms 25408 KB Output is correct
5 Correct 13 ms 25436 KB Output is correct
6 Correct 13 ms 25504 KB Output is correct
7 Correct 14 ms 25520 KB Output is correct
8 Correct 11 ms 25456 KB Output is correct
9 Correct 13 ms 25524 KB Output is correct
10 Correct 15 ms 25556 KB Output is correct
11 Correct 13 ms 25520 KB Output is correct
12 Correct 14 ms 25556 KB Output is correct
13 Correct 13 ms 25500 KB Output is correct
14 Correct 15 ms 25544 KB Output is correct
15 Correct 14 ms 25568 KB Output is correct
16 Correct 14 ms 25528 KB Output is correct
17 Correct 13 ms 25528 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 114 ms 27564 KB Output is correct
2 Correct 143 ms 28172 KB Output is correct
3 Correct 94 ms 26984 KB Output is correct
4 Correct 150 ms 28136 KB Output is correct
5 Correct 158 ms 28624 KB Output is correct
6 Correct 162 ms 28436 KB Output is correct
7 Correct 168 ms 28568 KB Output is correct
8 Correct 157 ms 28552 KB Output is correct
9 Correct 169 ms 28452 KB Output is correct
10 Correct 207 ms 28352 KB Output is correct
11 Correct 120 ms 31712 KB Output is correct

Subtask #4
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 25376 KB Output is correct
2 Correct 13 ms 25376 KB Output is correct
3 Correct 12 ms 25452 KB Output is correct
4 Correct 12 ms 25408 KB Output is correct
5 Correct 13 ms 25436 KB Output is correct
6 Correct 13 ms 25504 KB Output is correct
7 Correct 14 ms 25520 KB Output is correct
8 Correct 11 ms 25456 KB Output is correct
9 Correct 13 ms 25524 KB Output is correct
10 Correct 15 ms 25556 KB Output is correct
11 Correct 13 ms 25520 KB Output is correct
12 Correct 14 ms 25556 KB Output is correct
13 Correct 13 ms 25500 KB Output is correct
14 Correct 15 ms 25544 KB Output is correct
15 Correct 14 ms 25568 KB Output is correct
16 Correct 14 ms 25528 KB Output is correct
17 Correct 13 ms 25528 KB Output is correct
18 Correct 114 ms 27564 KB Output is correct
19 Correct 143 ms 28172 KB Output is correct
20 Correct 94 ms 26984 KB Output is correct
21 Correct 150 ms 28136 KB Output is correct
22 Correct 158 ms 28624 KB Output is correct
23 Correct 162 ms 28436 KB Output is correct
24 Correct 168 ms 28568 KB Output is correct
25 Correct 157 ms 28552 KB Output is correct
26 Correct 169 ms 28452 KB Output is correct
27 Correct 207 ms 28352 KB Output is correct
28 Correct 120 ms 31712 KB Output is correct
29 Correct 142 ms 33344 KB Output is correct
30 Correct 125 ms 30496 KB Output is correct
31 Correct 244 ms 35260 KB Output is correct
32 Correct 630 ms 45604 KB Output is correct
33 Correct 265 ms 35740 KB Output is correct
34 Correct 344 ms 36152 KB Output is correct
35 Correct 174 ms 32760 KB Output is correct
36 Correct 112 ms 30004 KB Output is correct
37 Correct 135 ms 30924 KB Output is correct
38 Correct 205 ms 31084 KB Output is correct
39 Correct 202 ms 31152 KB Output is correct
40 Correct 204 ms 31160 KB Output is correct
41 Correct 211 ms 31248 KB Output is correct
42 Correct 210 ms 31096 KB Output is correct
43 Correct 242 ms 33892 KB Output is correct
44 Correct 253 ms 33776 KB Output is correct
45 Correct 245 ms 33992 KB Output is correct
46 Correct 259 ms 33956 KB Output is correct
47 Correct 249 ms 33824 KB Output is correct
48 Correct 323 ms 32972 KB Output is correct
49 Correct 343 ms 33096 KB Output is correct
50 Correct 310 ms 33248 KB Output is correct
51 Correct 324 ms 33308 KB Output is correct
52 Correct 324 ms 32972 KB Output is correct
53 Correct 328 ms 32924 KB Output is correct
54 Correct 317 ms 33024 KB Output is correct