Submission #526817

#	Time	Username	Problem	Language	Result	Execution time	Memory
526817		beepbeepsheep	Izbori (COCI22_izbori)	C++17	0 / 110	91 ms	62872 KiB

Main

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

#define ll long long
#define ii pair<ll,ll>
#define endl '\n'
const ll inf=1e15;
const ll mod=1e9+7;
const ll maxn=2e5+5;

vector<ll> v;
ll arr[maxn];
vector<ll> cnt[maxn];
struct node{
    ll s,e,m,val,flag;
    node *l,*r;
    node(ll S, ll E){
        s=S,e=E,m=(s+e)>>1,val=0,flag=0;
        if (s!=e){
            l=new node(s,m),r=new node(m+1,e);
        }
    }
    void maintain(){
        if (flag==0) return;
        if (s!=e){
            l->flag+=flag;
            r->flag+=flag;
        }
        val+=(e-s+1)*flag;
        flag=0;
    }
    void reset(){
        if (s!=e && val!=0) {
            l->reset();
            r->reset();
        }
        val=0;
    }
    void upd(ll x, ll y, ll v){
        if (x<=s && e<=y) {
            flag+= v;
            return;
        }
        if (x>m) r->upd(x,y,v);
        else if (y<=m) l->upd(x,y,v);
        else l->upd(x,y,v),r->upd(x,y,v);
        l->maintain(),r->maintain();
        val=l->val+r->val;
    }
    ll query(ll x, ll y){
        maintain();
        if (x<=s && e<=y) return val;
        if (x>m) return r->query(x,y);
        if (y<=m) return l->query(x,y);
        return l->query(x,y)+r->query(x,y);
    }
}*root;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n;
    cin>>n;
    for (int i=0;i<n;i++){
        cin>>arr[i];
        v.push_back(arr[i]);
        cnt[i].emplace_back(0);
    }
    sort(v.begin(),v.end());
    vector<ll> newv;
    for (auto u:v){
        if (newv.empty() || newv.back()!=u) newv.push_back(u);
    }
    for (int i=0;i<n;i++){
        arr[i]=lower_bound(newv.begin(),newv.end(),arr[i])-newv.begin();
        cnt[arr[i]].emplace_back(i+1);
    }
    for (int i=0;i<newv.size();i++){
        cnt[i].emplace_back(n+1);
    }
    root=new node(-maxn,maxn);
    ll ans=0;
    for (int i=0;i<newv.size();i++){
        ll s=0,p=0; //s is running sum, p is prefix of all answers
        root->reset();
        root->upd(0,0,1);
        for (int j=1;j<cnt[i].size();j++){
            ll dis=cnt[i][j]-cnt[i][j-1]-1;
            if (dis) { //last seen to now
                p -= root->query(s - dis, s - 1);
                root->upd(s - dis, s - 1, 1);
                s -= dis;
                ans += p;
            }
            if (cnt[i][j]!=n+1) {
                p += root->query(s, s);
                root->upd(s+1, s+1, 1);
                s++;
                ans += p;
            }
        }
    }
    cout<<ans;
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:77:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for (int i=0;i<newv.size();i++){
      |                  ~^~~~~~~~~~~~
Main.cpp:82:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for (int i=0;i<newv.size();i++){
      |                  ~^~~~~~~~~~~~
Main.cpp:86:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |         for (int j=1;j<cnt[i].size();j++){
      |                      ~^~~~~~~~~~~~~~

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