oj.uz

Submission #893678

# Submission time Handle Problem Language Result Execution time Memory
893678 2023-12-27T09:02:58 Z vjudge1 Izbori (COCI22_izbori) C++17
25 / 110
 1811 ms 4304 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 + 5, bruh = 450;
 
int a[N], n, k;
int cnt[N];
int cnt1[N];
int mp[N * 2 + 1];
 
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(int j = 1; j <= cur; j++){
        int sz = cnt[j];
   		if(sz > bruh){
            memset(mp, 0, sizeof(mp));
	        ll cur = 0, act = 0;
	        ans = (1LL * (n * (n + 1))) / 2LL;
	        for(int i = 1; i <= n; i++){
		        if(a[i] == j) cur--;
		        else cur++;
		        mp[cur + n]++;
	        }
	        cur = 0;
	        for(ll i = 1; i <= n; i++){
		        ans -= mp[act + n];
		        if(a[i] == j){
			        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 1 ms 2396 KB Output is correct
3 Correct 4 ms 2652 KB Output is correct
4 Correct 4 ms 2652 KB Output is correct
5 Correct 4 ms 2396 KB Output is correct
6 Correct 4 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 1 ms 2396 KB Output is correct
3 Correct 4 ms 2652 KB Output is correct
4 Correct 4 ms 2652 KB Output is correct
5 Correct 4 ms 2396 KB Output is correct
6 Correct 4 ms 2652 KB Output is correct
7 Correct 12 ms 2648 KB Output is correct
8 Correct 2 ms 2652 KB Output is correct
9 Correct 26 ms 2688 KB Output is correct
10 Correct 27 ms 2904 KB Output is correct
11 Correct 26 ms 2664 KB Output is correct
12 Correct 25 ms 2688 KB Output is correct
13 Correct 25 ms 2684 KB Output is correct
14 Correct 25 ms 2652 KB Output is correct
15 Correct 25 ms 2904 KB Output is correct
16 Correct 27 ms 2652 KB Output is correct
17 Correct 27 ms 2652 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1811 ms 4304 KB Output isn't correct
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 1 ms 2396 KB Output is correct
3 Correct 4 ms 2652 KB Output is correct
4 Correct 4 ms 2652 KB Output is correct
5 Correct 4 ms 2396 KB Output is correct
6 Correct 4 ms 2652 KB Output is correct
7 Correct 12 ms 2648 KB Output is correct
8 Correct 2 ms 2652 KB Output is correct
9 Correct 26 ms 2688 KB Output is correct
10 Correct 27 ms 2904 KB Output is correct
11 Correct 26 ms 2664 KB Output is correct
12 Correct 25 ms 2688 KB Output is correct
13 Correct 25 ms 2684 KB Output is correct
14 Correct 25 ms 2652 KB Output is correct
15 Correct 25 ms 2904 KB Output is correct
16 Correct 27 ms 2652 KB Output is correct
17 Correct 27 ms 2652 KB Output is correct
18 Incorrect 1811 ms 4304 KB Output isn't correct
19 Halted 0 ms 0 KB -