Submission #927096

#	Time	Username	Problem	Language	Result	Execution time	Memory
927096		NintsiChkhaidze	Sum Zero (RMI20_sumzero)	C++17	0 / 100	10 ms	9048 KiB

sumzero

#include <bits/stdc++.h>
#define ll long long
#define s second
#define f first
#define pb push_back
#define pii pair <int,int>
#define left (h<<1),l,(l + r)/2
#define right ((h<<1)|1),(l + r)/2 + 1,r
#define int ll
using namespace std;

const int N = 4e5 + 5;

int a[N],p[N],last[N],vl[N];

struct node{
	int ans=0,pref=0,suf=0;
	int r=0,l=0,len=0;
} t[4*N];

node merge(node x,node y){
	node c;
	c.l = x.l,c.r= y.r;
	c.ans = x.ans + y.ans;
	c.len = x.len + y.len;
	// cout<<c.l<<" && "<<c.r<<endl;

	// cout<<x.suf<<" "<<y.pref<<endl;
	if (x.suf == 0 || y.pref == 0) {
		c.pref = x.pref;
		c.suf = y.suf;
		return c;
	}

	// cout<<x.r - x.suf<<endl;
	//neli jer
	int k = -1;
	for (int i = y.l; i <= y.l + y.pref - 1; i++){
		if (vl[i] >= x.r - x.suf) {k = i; break;}
 	}

	if (k != -1){
		c.ans++;
		c.pref = min(x.pref,vl[k] - x.l + 1);
		c.suf = min(y.suf,y.r - k);
	}else{
		c.pref = x.pref;
		c.suf = y.suf;
		if (y.suf == y.len) c.suf += x.suf;
		if (x.pref == x.len) c.pref += y.pref;
	}

	// cout<<"ans=  "<<c.ans<<" "<<c.pref<<" "<<c.suf<<endl;
	return c;
}

void build(int h,int l,int r){
	t[h].l = l;
	t[h].r = r;
	t[h].len = r - l + 1;
	if (l == r){
		t[h].ans = 0;
		t[h].pref = t[h].suf = 1;
		if (a[l] == 0) {
			t[h].ans = 1;
			t[h].pref = t[h].suf = 0;
		}
		return;
	}
	build(left);
	build(right);
	t[h] = merge(t[h*2],t[h*2+1]);
	// cout<<t[h].l<<" "<<t[h].r<<" ans = "<<t[h].ans<<endl;
}

node get(int h,int l,int r,int L,int R){
	if (r < L || R < l) return {};
	if (L <= l && r <= R) return t[h];
	return merge(get(left,L,R),get(right,L,R));
}

signed main(){
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);

	int n;
	cin>>n;

	vector <int> vec;
	map <int,int> mp;
	vec.pb(0);
	for(int i=1;i<=n;i++){
		cin>>a[i];
		p[i]=p[i-1]+a[i];
		vec.pb(p[i]);
	}

	sort(vec.begin(),vec.end());
	int val=0;
	for (int i=0;i<vec.size();i++){
		if (!i || vec[i] != vec[i - 1]) {
			++val;
			mp[vec[i]] = val;
		}
	}

	for (int i = 0; i <= n; i++)
		p[i] = mp[p[i]],last[p[i]] = -1;

	last[p[0]] = 0;
	for (int i = 1; i <= n; i++){
		vl[i] = last[p[i]];
		// cout<<vl[i]<<" ";
		last[p[i]] = i;
	}
	// cout<<endl;

	build(1,1,n);
	int q;
	cin>>q;

	while(q--){
		int l,r,ans=0;
		cin>>l>>r;
		node res = get(1,1,n,l,r);
		cout<<res.ans<<endl;
	}
}

Compilation message (stderr)

sumzero.cpp: In function 'int main()':
sumzero.cpp:99:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |  for (int i=0;i<vec.size();i++){
      |               ~^~~~~~~~~~~
sumzero.cpp:122:11: warning: unused variable 'ans' [-Wunused-variable]
  122 |   int l,r,ans=0;
      |           ^~~

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