Submission #65275429

---

Source Code Expand

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
mt19937 mt(time(NULL));
struct node{
	int val,sz,prior;
	ll sum[2];
	node*l,*r;
	node(){
		val=sum[0]=sum[1]=0;
		sz=0;
		prior=mt()>>1;
		l=r=nullptr;
	}
	node(int x){
		val=sum[0]=x;
		sum[1]=0;
		sz=1;
		prior=mt()>>1;
		l=r=nullptr;
	}
};
typedef node* pnode;
int sz(pnode&p){return p?p->sz:0;}
pll sum(pnode&p){return p?pll{p->sum[0],p->sum[1]}:pll{0,0};}
void calc(pnode&p){
	if(!p)return;
	p->sz=sz(p->l)+sz(p->r)+1;
	auto suml=sum(p->l);
	auto sumr=sum(p->r);
	if((sz(p->l)+1)&1)swap(sumr.first,sumr.second);
	p->sum[0]=suml.first+sumr.first;
	p->sum[1]=suml.second+sumr.second;
	p->sum[sz(p->l)&1]+=p->val;
}
void split(pnode p,int key,pnode&l,pnode&r){// <=key, >key
	if(!p)return void(l=r=0);
	if(key>=(p->val))split(p->r,key,p->r,r),l=p;
	else split(p->l,key,l,p->l),r=p;
	calc(p);
}
void Merge(pnode&p,pnode l,pnode r){
    if(!l||!r)p=l?l:r;
    else if(l->prior>r->prior)Merge(l->r,l->r,r),p=l;
    else Merge(r->l,l,r->l),p=r;
    calc(p);
}
void Insert(pnode&p,int val){
	pnode l,r;
	split(p,val,l,r);
	Merge(p,l,new node(val));
	Merge(p,p,r);
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	pnode root=0;
	int q;
	cin>>q;
	ll lst=0;
	while(q--){
		int y;
		cin>>y;
		int x=(y+lst)%(1000000000) +1;
		Insert(root,x);
		cout<<(lst=(root->sum[0]))<<"\n";
	}
	return 0;
}

Submission Info

Judge Result