Submission #644097

#	Time	Username	Problem	Language	Result	Execution time	Memory
644097		badmachine77	Sum Zero (RMI20_sumzero)	C++17	61 / 100	394 ms	26444 KiB

sumzero

/**
* user:  lendvaj-c30
* fname: Dorijan
* lname: Lendvaj
* task:  SumZero
* score: 100.0
* date:  2020-12-04 07:54:53.165994
*/
#include <bits/stdc++.h>
#define x first
#define y second
#define pii pair<int,int>
using ll=long long;
#define pll pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define eb emplace_back
#define all(a) begin(a),end(a)
using namespace std;

const int N=400010,MOD=1e9+7,LOG=7,B=6;
const char en='\n';
const ll LLINF=1ll<<60;

void compress(vl&v)
{
	vl v1=v;
	sort(all(v1));
	for (auto&a: v) a=lower_bound(all(v1),a)-v1.begin();
}

int n,q,cn[N],cncn[5000],ma,par[LOG+2][N],po[20];

void add(int a)
{
	--cncn[cn[a]];
	++cn[a];
	if (cn[a]>3) while (1);
	if (cn[a]==ma+1 && cncn[cn[a]]==0) ++ma;
	++cncn[cn[a]];
}

void rem(int a)
{
	--cncn[cn[a]];
	if (cn[a]==ma && cncn[cn[a]]==0) --ma;
	--cn[a];
	++cncn[cn[a]];
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	vl v;
	v.pb(0);
	ll s=0;
	for (int i=0;i<n;++i)
	{
		ll a;
		cin>>a;
		s+=a;
		v.pb(s);
	}
	compress(v);
	int r=-1;
	for (int l=0;l<=n;++l)
	{
		while (r<n && ma<=1) add(v[++r]);
		if (ma==2) par[0][l]=r;
		else par[0][l]=n+1;
		rem(v[l]);
		//cout<<l<<' '<<r<<en;
	}
	po[0]=1;
	for (int i=1;i<=LOG;++i) po[i]=po[i-1]*B;
	par[0][n+1]=n+1;
	for (int j=1;j<=LOG;++j) for (int i=0;i<=n+1;++i)
	{
		int u=i;
		for (int k=0;k<B;++k) u=par[j-1][u];
		par[j][i]=u;
	}
	cin>>q;
	while (q--)
	{
		int l,r;
		cin>>l>>r;
		--l;
		int an=0;
		for (int j=LOG;j>=0;--j) while (par[j][l]<=r) an+=po[j],l=par[j][l];
		cout<<an<<en;
	}
	
}

• Subtask 1: 22 / 22
• Subtask 2: 39 / 39
• Subtask 3: 0 / 39