oj.uz

Submission #945119

# Submission time Handle Problem Language Result Execution time Memory
945119 2024-03-13T12:25:41 Z beepbeepsheep Izbori (COCI22_izbori) C++17
0 / 110
 30 ms 53556 KB 
#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+2000002].empty() || vis[l+2000002].back()!=x) 
    		vis[l+2000002].emplace_back(x);
    	if (vis[r+2000002].empty() || vis[r+2000002].back()!=x) 
    		vis[r+2000002].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<4000005;i++){
    	for (auto u:vis[i]){
    		can[u].emplace_back(i-2000002);
    	}
    }
    for (int i=1;i<=n;i++){
    	if (adj[i].size()>1) ans+=solve(i);
    }
    cout<<ans;
    return 0;
}

Compilation message

Main.cpp: In function 'long long int solve(long long int)':
Main.cpp:39:19: 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.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 51372 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 51372 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 30 ms 53556 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 51372 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -