제출 #540867

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
540867		AlperenT	Izbori (COCI22_izbori)	C++17	110 / 110	630 ms	45604 KiB

Main

#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 / 10
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 70 / 70