Submission #528658

#	Time	Username	Problem	Language	Result	Execution time	Memory
528658		penguinhacker	Izbori (COCI22_izbori)	C++14	110 / 110	919 ms	23740 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=2e5;
int n, a[mxN];
map<int, vector<int>> mp;
ll ans;

struct {
	int sum[1<<20], lz[1<<20];
	ll isum[1<<20];
	void psh(int u, int l, int r) {
		if (lz[u]) {
			sum[u]+=lz[u]*(r-l+1);
			isum[u]+=(ll)lz[u]*(r-l+1)*(l+r)/2;
			if (l!=r)
				lz[2*u]+=lz[u], lz[2*u+1]+=lz[u];
			lz[u]=0;
		}
	}
	void upd(int ql, int qr, int x, int u=1, int l=0, int r=2*n) {
		psh(u, l, r);
		if (l>qr||r<ql)
			return;
		if (ql<=l&&r<=qr) {
			lz[u]+=x;
			psh(u, l, r);
			return;
		}
		int mid=(l+r)/2;
		upd(ql, qr, x, 2*u, l, mid);
		upd(ql, qr, x ,2*u+1, mid+1, r);
		sum[u]=sum[2*u]+sum[2*u+1];
		isum[u]=isum[2*u]+isum[2*u+1];
	}
	ll qry(int ql, int qr, int t, int u=1, int l=0, int r=2*n) {
		psh(u, l, r);
		if (l>qr||r<ql)
			return 0;
		if (ql<=l&&r<=qr)
			return t==0?sum[u]:isum[u];
		int mid=(l+r)/2;
		return qry(ql, qr, t, 2*u, l, mid)+qry(ql, qr, t, 2*u+1, mid+1, r);
	}
} st;

void solve(vector<int> v) {
	int pref=n;
	vector<ar<int, 2>> rb;
	if (v[0]) {
		st.upd(n-v[0], n-1, 1);
		rb.push_back({n-v[0], n-1});
		pref-=v[0];
	}
	for (int i=0; i<v.size(); ++i) {
		++pref;
		ans+=st.qry(0, pref-1, 0);
		//cout << ans << "\n";
		st.upd(pref, pref, 1);
		rb.push_back({pref, pref});
		if (i+1<v.size()&&v[i]+1<v[i+1]||i+1==v.size()&&v[i]<n-1) {
			int len=(i+1==v.size()?n-1:v[i+1]-1)-v[i];
			//cout << "len " << len << endl;
			ans+=len*st.qry(0, pref-len-1, 0);
			ans+=(pref-1)*st.qry(pref-len, pref-2, 0)-st.qry(pref-len, pref-2, 1);
			st.upd(pref-len, pref-1, 1);
			rb.push_back({pref-len, pref-1});
			pref-=len;
		}
		//cout << ans << "\n";
	}
	for (ar<int, 2> x : rb)
		st.upd(x[0], x[1], -1);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i=0; i<n; ++i) {
		cin >> a[i];
		mp[a[i]].push_back(i);
	}
	st.upd(n, n, 1);
	for (auto x : mp)
		solve(x.second); //  , cout << ans << "\n";
	cout << ans;
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void solve(std::vector<int>)':
Main.cpp:58:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for (int i=0; i<v.size(); ++i) {
      |                ~^~~~~~~~~
Main.cpp:64:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |   if (i+1<v.size()&&v[i]+1<v[i+1]||i+1==v.size()&&v[i]<n-1) {
      |       ~~~^~~~~~~~~
Main.cpp:64:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |   if (i+1<v.size()&&v[i]+1<v[i+1]||i+1==v.size()&&v[i]<n-1) {
      |                                    ~~~^~~~~~~~~~
Main.cpp:64:19: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   64 |   if (i+1<v.size()&&v[i]+1<v[i+1]||i+1==v.size()&&v[i]<n-1) {
Main.cpp:65:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |    int len=(i+1==v.size()?n-1:v[i+1]-1)-v[i];
      |             ~~~^~~~~~~~~~

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