Submission #945115

#	Time	Username	Problem	Language	Result	Execution time	Memory
945115		beepbeepsheep	Izbori (COCI22_izbori)	C++17	110 / 110	166 ms	21696 KiB

Main

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

#define ll long long
#define ii pair<ll,ll>
#ifndef DEBUG
#define cerr if (0) cerr
#define endl '\n'
#endif

const ll maxn=2e5+5;
const ll inf=1e15;

ll n;
vector<ll> adj[maxn];
ll fen[maxn];

void upd(ll x){
    while (x<maxn){
        fen[x]++;
        x+=(x&-x);
    }
}
ll query(ll x){
    ll ans=0;
    while (x){
        ans+=fen[x];
        x-=(x&-x);
    }
    return ans;
}
ll solve(ll x){
    adj[x].emplace_back(n+1);
    vector<ii> ranges;
    ranges.emplace_back(0,-adj[x][0]+1);
    for (int i=1;i<adj[x].size();i++){
        ll prv=ranges.back().second;
        ranges.emplace_back(prv+1,prv+2-(adj[x][i]-adj[x][i-1]));
    }
    //ranges of negative values
    vector<ll> can;
    can.emplace_back(-inf);
    for (auto [l,r]:ranges){
        can.emplace_back(l);
        can.emplace_back(l+1);
        can.emplace_back(r);
        can.emplace_back(r+1);
    }
    ll ans=0;
    sort(can.begin(),can.end());
    can.erase(unique(can.begin(),can.end()),can.end());
    for (int i=1;i<=can.size();i++) fen[i]=0;
    for (auto [l,r]:ranges){
        ll s=lower_bound(can.begin(),can.end(),r)-can.begin();
        ll e=lower_bound(can.begin(),can.end(),l)-can.begin();
        for (int i=e;i>=s;i--){
            ans+=query(i-1);
            upd(i);
        }
    }
    return ans;
}
map<ll,ll> m;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll ele,cnt=1;
    cin>>n;
    for (int i=1;i<=n;i++){
        cin>>ele;
        if (m.count(ele)) ele=m[ele];
        else{
        	m[ele]=cnt;
        	ele=cnt;
        	cnt++;
        }
        adj[ele].emplace_back(i);
    }
    ll ans=0;
    for (int i=1;i<=n;i++){
        if (adj[i].size()>1) ans+=solve(i);
        else ans+=adj[i].size();
    }
    cout<<ans;
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'long long int solve(long long int)':
Main.cpp:36:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for (int i=1;i<adj[x].size();i++){
      |                  ~^~~~~~~~~~~~~~
Main.cpp:52:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for (int i=1;i<=can.size();i++) fen[i]=0;
      |                  ~^~~~~~~~~~~~

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