oj.uz

Submission #540857

# Submission time Handle Problem Language Result Execution time Memory
540857 2022-03-21T20:55:54 Z AlperenT Izbori (COCI22_izbori) C++17
0 / 110
 108 ms 27824 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){
        push(v, tl, tr);

        if(l > r) return {0, 0};
        else{
            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){
        push(v, tl, tr);

        if(l > r) return;
        else{
            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.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;
        }

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

    cout << ans;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 25420 KB Output is correct
2 Correct 11 ms 25428 KB Output is correct
3 Correct 12 ms 25428 KB Output is correct
4 Incorrect 12 ms 25428 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 25420 KB Output is correct
2 Correct 11 ms 25428 KB Output is correct
3 Correct 12 ms 25428 KB Output is correct
4 Incorrect 12 ms 25428 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 108 ms 27824 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 25420 KB Output is correct
2 Correct 11 ms 25428 KB Output is correct
3 Correct 12 ms 25428 KB Output is correct
4 Incorrect 12 ms 25428 KB Output isn't correct
5 Halted 0 ms 0 KB -