Submission #945120

#	Time	Username	Problem	Language	Result	Execution time	Memory
945120		beepbeepsheep	Izbori (COCI22_izbori)	C++17	0 / 110	39 ms	53572 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=1e9;
     
    ll n;
    vector<int> adj[maxn];
    ll fen[maxn];
    vector<int> vis[2*maxn];
    vector<int> can[maxn];
    vector<pair<int,int>> rngs[maxn];
    void precomp(ll x){
        adj[x].emplace_back(n+1);
        rngs[x].emplace_back(0,-adj[x][0]+1);
        ll sz=adj[x].size();
        for (int i=1;i<sz;i++){
            ll prv=rngs[x].back().second;
            rngs[x].emplace_back(prv+1,prv+2-(adj[x][i]-adj[x][i-1]));
        }
        //rngs of negative values
        can[x].emplace_back(-inf);
        for (auto [l,r]:rngs[x]){
        	if (vis[l+200002].empty() || vis[l+200002].back()!=x) 
        		vis[l+2000002].emplace_back(x);
        	if (vis[r+200002].empty() || vis[r+200002].back()!=x) 
        		vis[r+200002].emplace_back(x);
        }
    }
    ll solve(ll x){
    	ll ans=0;
        for (int i=1;i<=can[x].size();i++) fen[i]=0;
        ll pos=lower_bound(can[x].begin(),can[x].end(),0)-can[x].begin();
        ll tot=0;
        for (auto [l,r]:rngs[x]){
            while (can[x][pos]>=r){
                tot-=fen[pos];
                ans+=tot;
                fen[pos]++;
                pos--;
            }
            tot+=fen[pos+1]+fen[pos+2];
            pos+=2;
        }
        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) precomp(i);
            else ans+=adj[i].size();
        }
        for (int i=0;i<400005;i++){
        	for (auto u:vis[i]){
        		can[u].emplace_back(i-200002);
        	}
        }
        for (int i=1;i<=n;i++){
        	if (adj[i].size()>1) ans+=solve(i);
        }
        cout<<ans;
        return 0;
    }

Compilation message (stderr)

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

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