Submission #902173

#	Time	Username	Problem	Language	Result	Execution time	Memory
902173		Isam	Izbori (COCI22_izbori)	C++17	40 / 110	3013 ms	6984 KiB

Main

#include<bits/stdc++.h>
using namespace std;
constexpr int sz = 300005;


int N, A[sz];
long long pref[sz], tree[sz];

unordered_set<int> st;

inline void update(int pos, long long val){
	while(pos <= N + 5){
		tree[pos] += val;
		pos += (pos & (-pos));
	}
	return;
}

long long get_ans(int l, int r){
	if(l != 1) return get_ans(1, r) - get_ans(1, l - 1);
	long long res(0);
	while(r > 0){
		res += tree[r];
		r -= (r & (-r));
	}
	return res;
}

signed main(){
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> N;
	for(register int i = 1; i <= N; ++i){
		cin >> A[i];
		st.insert(A[i]);
	}
	long long ans(0);
	for(auto &tot : st){
		for(register int i = 1; i <= N + 10; ++i) tree[i] = 0;
		long long mn = N + 5;
		for(register int i = 1; i <= N; ++i){
		    pref[i] = pref[i - 1] + (tot == A[i] ? 1 : -1);
		    mn = min(mn, pref[i]);
		}
		mn = abs(mn) + 5;
		update(mn, 1);
		for(register int i = 1; i <= N ;++i){
			pref[i] += mn;
			update(pref[i], 1);
			ans += get_ans(1, pref[i] - 1);
		}
	}
	cout << ans << '\n';
	return 0;
}
/*

1 1 2 1 2

-1 -1 1 -1 1




*/

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:32:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   32 |  for(register int i = 1; i <= N; ++i){
      |                   ^
Main.cpp:38:20: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   38 |   for(register int i = 1; i <= N + 10; ++i) tree[i] = 0;
      |                    ^
Main.cpp:40:20: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   40 |   for(register int i = 1; i <= N; ++i){
      |                    ^
Main.cpp:46:20: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   46 |   for(register int i = 1; i <= N ;++i){
      |                    ^

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 0 / 70