Submission #970440

#	Time	Username	Problem	Language	Result	Execution time	Memory
970440		PenguinsAreCute	Izbori (COCI22_izbori)	C++17	110 / 110	2126 ms	15528 KiB

Main

// is sqrt intended
// and is n^1.5 log^0.5 n intended
// i guess the tl is 3sec so
#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int hi(int a, int b, int c, int d, int e) {
	// [a,b] + [c,d] <= e.
	if(b-a<=d-c) {swap(a,c);swap(b,d);}
	if(e<a+c) return 0;
	if(e>b+d) return (b-a+1)*(d-c+1);
	if(e<=a+d) return (e-a-c+1)*(e-a-c+2)/2;
	if(e>=b+c) return (b-a+1)*(d-c+1)-(b+d-e)*(b+d+1-e)/2;
	return (e-a-d) * (d-c+1) + (d-c+1) * (d-c+2) / 2;
}
int calcA(int n, vector<int> &v) {
	int s = v.size(), ans = 0;
	for(int i=0;i<s;i++) for(int j=i;j<s;j++) {
		int l = (i?v[i-1]+1:0);
		int r = (j==s-1?n-1:v[j+1]-1);
		ans += hi(-v[i],-l,v[j],r,(j-i)<<1);
	}
	return ans;
}
// 2pre[r] - r > 2pre[l] - l
struct fenwick {
	int n; vector<int> fw;
	fenwick(int _n): n(_n), fw(_n+1,0) {}
	inline void up(int x) {for(;x<=n;x+=(x&(-x))) ++fw[x];}
	inline int qry(int x) {
		int ans = 0;
		for(;x;x-=(x&(-x))) ans+=fw[x];
		return ans;
	}
};
int calcB(int n, vector<int> &v) {
	fenwick fw(n<<1|1);
	fw.up(n+1);
	int a[n]; fill(a,a+n,-1); for(auto i: v) a[i]=1;
	int ans = 0;
	for(int i=0,s=0;i<n;i++) {
		s += a[i];
		ans += fw.qry(s+n);
		fw.up(s+n+1);
	}
	return ans;
}
main() {
	int n; cin >> n;
	int a[n], b[n]; for(int i=0;i<n;i++) {cin>>a[i];b[i]=a[i];}
	sort(b,b+n);
	for(int i=0;i<n;i++) a[i]=lower_bound(b,b+n,a[i])-b;
	vector<int> v[n];
	for(int i=0;i<n;i++) v[a[i]].push_back(i);
	int ans = 0;
	for(int i=0;i<n;i++) {
		/*
		if(calcA(n,v[i]) != calcB(n,v[i])) {
			for(auto j: v[i]) cout << j << " "; cout << "\n";
			cout << calcA(n,v[i]) << " " << calcB(n,v[i]);
			return -1;
		}
		*/
		ans += (v[i].size()<=500?calcA(n,v[i]):calcB(n,v[i]));
	}
	cout << ans;
}

Compilation message (stderr)

Main.cpp:48:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   48 | main() {
      | ^~~~

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