Submission #1129926

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129926		boris_7	Horses (IOI15_horses)	C++20	17 / 100	1105 ms	54096 KiB

horses

#include "horses.h"
#include<bits/stdc++.h>
int mod = 1e9+7;
using namespace std;
using ll = long long;

vector<ll>x,y,seg,segx;
set<ll>st;
__int128 n,loc=1,s=1;

void update(int l,int r,int u,int ind,int val){
	if(l==r){
		seg[u]=val;
		return;
	}
	int mid = (l+r)/2;
	if(ind<=mid) update(l,mid,u*2+1,ind,val);
	else update(mid+1,r,u*2+2,ind,val);
	seg[u]=(seg[u*2+1]*seg[u*2+2])%mod;
}

ll get(int l,int r,int u,int lx,int rx){
	if(l>=lx && r<=rx){
		return seg[u];
	}
	if(l>rx||r<lx){
		return 1;
	}
	int mid = (l+r)/2;
	return (get(l,mid,u*2+1,lx,rx)*get(mid+1,r,u*2+2,lx,rx))%mod;
}

void updatex(int l,int r,int u,int ind,int val){
	if(l==r){
		segx[u]=val;
		return;
	}
	int mid = (l+r)/2;
	if(ind<=mid) updatex(l,mid,u*2+1,ind,val);
	else updatex(mid+1,r,u*2+2,ind,val);
	segx[u]=max(segx[u*2+1],segx[u*2+2]);
}

ll getx(int l,int r,int u,int lx,int rx){
	if(l>=lx && r<=rx){
		return segx[u];
	}
	if(l>rx||r<lx){
		return 0;
	}
	int mid = (l+r)/2;
	return max(getx(l,mid,u*2+1,lx,rx),getx(mid+1,r,u*2+2,lx,rx));
}

ll pat(){

	ll mul = 1,indd=-1,ans=1,flag=0;
	auto itt = st.begin();

	for(auto it = st.begin();it!=st.end();it++){
		ll ind = -(*it);
		mul*=x[ind];
		itt=it;
		if(mul>1e18) {
			break;
		}
	}
	if(mul<=1e18) flag=1;
	if(mul!=1){
		mul=1;
		for(auto it = itt;;it--){
			ll ind = -(*it);
			mul*=x[ind];
			ll mx = getx(0,s-1,0,ind,s-1);

			if(mul*mx>ans){
				ans = (mul*mx);
				indd = ind;
			}
			if(it==st.begin())break;
			if(mul>1e18) break;
		}
	}
	if(x[0]==1 && flag){
		ll ind = 0;
		ll mx = getx(0,s-1,0,ind,s-1);
		if(mx>ans){
			ans = (mx)%mod;
			indd = ind;
		}

	}
	return (get(0,s-1,0,0,indd)*getx(0,s-1,0,indd,s-1))%mod;
}

int init(int N, int X[], int Y[]) {
	n = N;
	while(s<n)s*=2;
	seg = segx = vector<ll>(2*s,1);
	for(int i = 0;i<n;i++) {
		x.push_back(X[i]);
		update(0,s-1,0,i,X[i]);
		if(X[i]!=1)st.insert(-i);
	}
	for(int i = 0;i<n;i++) y.push_back(Y[i]),updatex(0,s-1,0,i,Y[i]);
	return pat();
}

int updateX(int pos, int val) {
	if(x[pos]!=1) st.erase(-pos);
	x[pos]=val;
	if(x[pos]!=1) st.insert(-pos);
	update(0,s-1,0,pos,val);
	return pat();
}

int updateY(int pos, int val) {
	y[pos]=val;
	updatex(0,s-1,0,pos,val);
	return pat();
}

• Subtask 1: 17 / 17
• Subtask 2: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 23
• Subtask 5: 0 / 23