oj.uz

Submission #893671

# Submission time Handle Problem Language Result Execution time Memory
893671 2023-12-27T08:59:30 Z vjudge1 Izbori (COCI22_izbori) C++17
25 / 110
 3000 ms 6100 KB 
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <bitset>
#include <cstdint>
#include <cassert>
#include <functional>
#include <complex>
#include <climits>
#include <random>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")

using namespace std;

#define pb push_back
#define F first
#define S second
#define ll long long
#define ull unsigned long long
#define all(x) x.begin(), x.end() 
#define speed ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
const int mod = (int) 1e9 + 7;
const int N = (int) 2e5 + 100, bruh = 450;
 
ll a[N], n, k;
map<int, int> cnt;
ll cnt1[N];
 
signed main(){
   	speed;
   	cin >> n;
    vector<pair<int, int>> v;
   	for(int i = 1; i <= n; i++){
   		cin >> a[i];
        v.pb({a[i], i});
   	} 
    sort(all(v));
    int prev = -1, cur = 0;
    for(auto [x, y] : v){
        if(x != prev){
            ++cur;
            prev = x;
            a[y] = cur;
        }
        else a[y] = cur;
    }
    for(int i = 1; i <= n; i++){
        cnt[a[i]]++;
    }
   	ll ans = 0;
   	for(auto [x, sz] : cnt){
   		if(sz > bruh){
	   		ll mp[n * 2 + 1];
            for(int i = 0; i <= 2 * n + 1; i++) mp[i] = 0;
	        ll cur = 0, act = 0;
	        ans = (1LL * (n * (n + 1))) / 2LL;
	        for(ll i = 1; i <= n; i++){
		        if(a[i] == x) cur--;
		        else cur++;
		        mp[cur + n]++;
	        }
	        cur = 0;
	        for(ll i = 1; i <= n; i++){
		        ans -= mp[act + n];
		        if(a[i] == x){
			        cur--;
			        act--;
		        }
		        else{
			        cur++;
			        act++;
		        }
		        mp[cur + n]--;
	        }	
        }
   	}
   	for(int i = 1; i <= n; i++){
        memset(cnt1, 0, sizeof(cnt1));
   		int lst = -1, lstA = -1;
   		for(int j = i; j <= n; j++){
   			if((j - i + 1) > 2 * bruh) break;
   			if(a[j] == lstA) lst++;
   			++cnt1[a[j]];
   			int sz = (j - i) + 1;
   			if(lst > (sz / 2) && cnt[lstA] <= bruh) ans++;
   			else if(cnt1[a[j]] > (sz / 2) && cnt[a[j]] <= bruh){
   				ans++;
   				lst = cnt1[a[j]];
   				lstA = a[j];
   			}
   		}
   	}
   	cout << ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 2 ms 2460 KB Output is correct
3 Correct 8 ms 2652 KB Output is correct
4 Correct 8 ms 2648 KB Output is correct
5 Correct 8 ms 2652 KB Output is correct
6 Correct 8 ms 2652 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 2 ms 2460 KB Output is correct
3 Correct 8 ms 2652 KB Output is correct
4 Correct 8 ms 2648 KB Output is correct
5 Correct 8 ms 2652 KB Output is correct
6 Correct 8 ms 2652 KB Output is correct
7 Correct 23 ms 2652 KB Output is correct
8 Correct 3 ms 2652 KB Output is correct
9 Correct 49 ms 2688 KB Output is correct
10 Correct 49 ms 2652 KB Output is correct
11 Correct 50 ms 2708 KB Output is correct
12 Correct 54 ms 2648 KB Output is correct
13 Correct 49 ms 2648 KB Output is correct
14 Correct 52 ms 2708 KB Output is correct
15 Correct 49 ms 2648 KB Output is correct
16 Correct 51 ms 2652 KB Output is correct
17 Correct 51 ms 2648 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3052 ms 6100 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 2 ms 2460 KB Output is correct
3 Correct 8 ms 2652 KB Output is correct
4 Correct 8 ms 2648 KB Output is correct
5 Correct 8 ms 2652 KB Output is correct
6 Correct 8 ms 2652 KB Output is correct
7 Correct 23 ms 2652 KB Output is correct
8 Correct 3 ms 2652 KB Output is correct
9 Correct 49 ms 2688 KB Output is correct
10 Correct 49 ms 2652 KB Output is correct
11 Correct 50 ms 2708 KB Output is correct
12 Correct 54 ms 2648 KB Output is correct
13 Correct 49 ms 2648 KB Output is correct
14 Correct 52 ms 2708 KB Output is correct
15 Correct 49 ms 2648 KB Output is correct
16 Correct 51 ms 2652 KB Output is correct
17 Correct 51 ms 2648 KB Output is correct
18 Execution timed out 3052 ms 6100 KB Time limit exceeded
19 Halted 0 ms 0 KB -