oj.uz

Submission #893664

# Submission time Handle Problem Language Result Execution time Memory
893664 2023-12-27T08:51:33 Z vjudge1 Izbori (COCI22_izbori) C++17
0 / 110
 3000 ms 6340 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 + 1, bruh = 450;
 
ll a[N], n, k;
//int cnt[N];
map<int, int> cnt;
 
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 = 1;
    for(auto [x, y] : v){
        if(x != prev){
            a[y] = cur;
            prev = x;
            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++){
        int cnt1[n + 1];
        for(int i = 0; i < n + 1; i++) cnt1[i] = 0;
   		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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Runtime error 1 ms 532 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Runtime error 1 ms 532 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1466 ms 4564 KB Output is correct
2 Correct 2627 ms 5844 KB Output is correct
3 Correct 862 ms 3544 KB Output is correct
4 Correct 2877 ms 6092 KB Output is correct
5 Execution timed out 3055 ms 6340 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Runtime error 1 ms 532 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -