Submission #194121

#	Time	Username	Problem	Language	Result	Execution time	Memory
194121		toma	Horses (IOI15_horses)	C++17	Compilation error	0 ms	0 KiB

horses

#include<bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define M (L+R)/2
#define N 500009
#define inf 99999999999
#define ll long long
#define mod 1000000007
using namespace std;

ll n,m,x[N],y[N],u,pos,X,ANS;
double A,B,T;
pair <double,ll> p;

struct node{
	ll nam;
	node *left,*right;
	node(): nam(1),left(NULL),right(NULL){}
};
node *root(NULL);

void add(node *&parent,ll L,ll R,ll ind){
	if(!parent){
		parent=new node();
	}
	if(L+1==R){
		parent->nam=x[ind]%mod;
		return;
	}
	if(ind<M){
		add(parent->left,L,M,ind);
	} else {
		add(parent->right,M,R,ind);
	}
	parent->nam=((parent->left?parent->left->nam:1)*(parent->right?parent->right->nam:1))%mod;
}

ll get(node *&parent,ll L,ll R,ll l,ll r){
	if(parent){
		if(L>=r || R<=l)return 1;
		if(l<=L && R<=r)return parent->nam;
		return (get(parent->left,L,M,l,r)*get(parent->right,M,R,l,r))%mod;
	}
	return 1;
}

struct nod{
	pair<double,ll> D;
	double b;
	nod *left,*right;
	nod(): D({0,0}),b(0),left(NULL),right(NULL){}
};
nod *rot(NULL);

void upd(nod *&parent,ll L,ll R,ll ind){
	if(!parent){
		parent=new nod();
	}
	if(L+1==R){
		parent->D={log(y[ind])+T,ind};
		return;
	}
	if(ind<M){
		upd(parent->left,L,M,ind);
	} else {
		upd(parent->right,M,R,ind);
	}
	A=B=0;
	if(parent->left)A=parent->left->D.f;
	if(parent->right)B=parent->right->D.f;
	if(A>=B ){
		parent->D=parent->left->D;
	} else {
		parent->D=parent->right->D;
	}
}

void ad(nod *&parent,ll L,ll R,ll l,ll r,double ba){
	if(parent){
		if(parent->b!=0){
			if(parent->left)parent->left->b+=parent->b;
			if(parent->right)parent->right->b+=parent->b;
			parent->D.f+=parent->b;
			parent->b=0;
		}
		if(L>=r || R<=l)return;
		if(l<=L && R<=r){
			if(parent->left)parent->left->b+=ba;
			if(parent->right)parent->right->b+=ba;
			parent->D.f+=ba;
			return;
		}
		ad(parent->left,L,M,l,r,ba);
		ad(parent->right,M,R,l,r,ba);
		A=B=0;
		if(parent->left)A=parent->left->D.f;
		if(parent->right)B=parent->right->D.f;
		if(A>=B){
			parent->D=parent->left->D;
		} else {
			parent->D=parent->right->D;
		}	
	}
}

pair<double,ll> ge(nod *&parent,ll L,ll R,ll l,ll r){
	if(parent){
		if(parent->b!=0){
			if(parent->left)parent->left->b+=parent->b;
			if(parent->right)parent->right->b+=parent->b;
			parent->D.f+=parent->b;
			parent->b=0;
		}
		if(L>=r || R<=l)return {0,0};
		if(l<=L && R<=r)return parent->D;
		ge(parent->left,L,M,l,r);
		ge(parent->right,M,R,l,r);
	}
	return {0,0};
}

int main(){

	ios::sync_with_stdio(0);
	
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>x[i];
		add(root,0,n,i);
	}
	T=0;
	for(int i=0;i<n;i++){
		cin>>y[i];
		T+=log(x[i]);
		upd(rot,0,n,i);
	}
	
	p=rot->D;
	ANS=get(root,0,n,0,p.s+1);
	ANS%=mod;
	ANS*=(y[p.s])%mod;
	ANS%=mod;
	cout<<ANS<<endl;
	
	cin>>m;
	while(m--){
		cin>>u>>pos>>X;
		if(u==1){
			ad(rot,0,n,pos,n,-log(x[pos]));
			x[pos]=X;
			ad(rot,0,n,pos,n,log(x[pos]));
			add(root,0,n,pos);
		} else {
			ad(rot,0,n,pos,pos+1,-log(y[pos]));
			y[pos]=X;
			ad(rot,0,n,pos,pos+1,log(y[pos]));
		}
		p=rot->D;
		ANS=get(root,0,n,0,p.s+1);
		ANS%=mod;
		ANS*=(y[p.s])%mod;
		ANS%=mod;
		cout<<ANS<<endl;
	}

	return 0;
}

Compilation message (stderr)

/tmp/cc0pIw1j.o: In function `main':
grader.c:(.text.startup+0x0): multiple definition of `main'
/tmp/cc0sTDFk.o:horses.cpp:(.text.startup+0x0): first defined here
/tmp/cc0pIw1j.o: In function `main':
grader.c:(.text.startup+0x2db): undefined reference to `init(int, int*, int*)'
grader.c:(.text.startup+0x71a): undefined reference to `updateX(int, int)'
grader.c:(.text.startup+0x8a6): undefined reference to `updateY(int, int)'
collect2: error: ld returned 1 exit status