oj.uz

Submission #711490

# Submission time Handle Problem Language Result Execution time Memory
711490 2023-03-17T05:48:04 Z devvops Izbori (COCI22_izbori) C++14
0 / 110
 1887 ms 4432 KB 
#include <bits/stdc++.h>
#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 = 500;

ll a[N], tree[N], n, k;
map<int, int> cnt;

void upd(int idx){
	for(int i = idx; i < N; i += i & -i){
		tree[i] += 1;
	}
}

ll get(int x){
	ll ans = 0;
	for (int i = x; i > 0; i -= i & -i) {
         ans += tree[i];
    }
    return ans;
}

signed main(){
   	speed;
   	cin >> n >> k;
   	for(int i = 1; i <= n; i++){
   		cin >> a[i];
   		cnt[a[i]]++;
   	} 
   	ll ans = 0;
   	for(auto i : cnt){
   		if(i.S > bruh){
   			memset(tree, 0, sizeof(tree));
	   		vector<int> v;
	   		for(int j = 1; j <= n; j++){
	   			if(a[j] == i.F) v.pb(1);
	   			else v.pb(-1);
	   		}
	   		int s = 0;
	   		upd(n + 1);
	   		for(int j = 0; j < n; j++){
	   			s += v[j];
	   			if(s < 0){
	   				upd(abs(s));
	   				ans += get(n) - get(abs(s));
	   			}
	   			else{
	   				upd(s + (n + 1));
	   				ans += get(n) - get(0);
	   				ans += get(n + s) - get(n);
	   			}
	   		}
   		}
   	}
   	for(int i = 1; i <= n; i++){
   		map<int, int> 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1887 ms 4432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -