Submission #527670

#	Time	Username	Problem	Language	Result	Execution time	Memory
527670		joelau	Izbori (COCI22_izbori)	C++14	0 / 110	160 ms	50176 KiB

Main

#include <bits/stdc++.h>
using namespace std;

long long N,A[200005];
vector<long long> A1, lst[200005];

struct node {
    long long s,e,m,v; pair<long long,long long> lazy; node *l, *r;
    node (long long S, long long E) {
        s = S, e = E, m = (s+e)/2, v = 0, lazy = make_pair(0,0);
        if (s != e) l = new node(s,m), r = new node(m+1,e);
    }
    void propo() {
        if (lazy == make_pair(0ll,0ll)) return;
        v += (e-s+1) * (e-s) / 2 * lazy.first + (e-s+1) * lazy.second;
        if (s != e) l->lazy.first += lazy.first, l->lazy.second += lazy.second, r->lazy.first += lazy.first, r->lazy.second += lazy.second;
        lazy = make_pair(0,0);
    }
    void update (long long x, long long y, long long a, long long b) {
        propo();
        if (s == x && e == y) lazy.first += a, lazy.second += b;
        else {
            if (y <= m) l -> update(x,y,a,b);
            else if (x > m) r -> update(x,y,a,b);
            else l -> update(x,m,a,b), r -> update(m+1,y,a,b+(m-x+1)*a);
            l->propo(), r->propo();
            v = l->v + r->v;
        }
    }
    long long query (long long x, long long y) {
        propo();
        if (s == x && e == y) return v;
        else if (y <= m) return l -> query(x,y);
        else if (x > m) return r -> query(x,y);
        else return l->query(x,m) + r->query(m+1,y);
    }
}*root;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> N;
    for (long long i = 0; i < N; ++i) {
        cin >> A[i];
        A1.push_back(A[i]);
    }
    sort(A1.begin(),A1.end());
    A1.resize(unique(A1.begin(),A1.end())-A1.begin());
    for (long long i = 0; i < N; ++i) {
        A[i] = lower_bound(A1.begin(),A1.end(),A[i])-A1.begin();
        lst[A[i]].push_back(lst[A[i]].size()*2-i+1);
    }
    root = new node(0,N*2);
    long long ans = 0;
    for (long long i = 0; i < N; ++i) if (!lst[i].empty()) {
        root -> update(N+lst[i][0]-1,N,1,1);
        root -> update(N+1,N*2,0,2-lst[i][0]);
        for (long long j = 1; j < lst[i].size(); ++j) {
            ans += root -> query(N+lst[i][j]-2,N+lst[i][j-1]-1);
            root -> update(N+lst[i][j]-1,N+lst[i][j-1],1,1);
            root -> update(N+lst[i][j-1]+1,N*2,0,lst[i][j-1]-lst[i][j]+2);
        }
        ans += root -> query(lst[i].size()*2-1,N+lst[i].back()-1);
        root -> update(N+lst[i][0]-1,N,-1,-1);
        root -> update(N+1,N*2,0,lst[i][0]-2);
        for (long long j = 1; j < lst[i].size(); ++j) {
            root -> update(N+lst[i][j]-1,N+lst[i][j-1],-1,-1);
            root -> update(N+lst[i][j-1]+1,N*2,0,lst[i][j]-lst[i][j-1]-2);
        }
    }
    cout << ans;

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:57:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for (long long j = 1; j < lst[i].size(); ++j) {
      |                               ~~^~~~~~~~~~~~~~~
Main.cpp:65:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for (long long j = 1; j < lst[i].size(); ++j) {
      |                               ~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 15
• Subtask 4: 0 / 70