Submission #1213056

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213056		Saul0906	Horses (IOI15_horses)	C++20	100 / 100	549 ms	83600 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
#define mid ((l+r)>>1)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define repr(a,b,c) for(int a=b-1; a>c-1; a--)
#define repa(a,b) for(auto a:b)
#define pii pair<int, int>
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define ll long long
#define pb push_back

using namespace std;

const ll inf=1e18, mod=1e9+7;
const int N=5e5+5;

struct segtree{
	segtree *left, *right;
	int l, r;
       	ll X, Y=0;
	segtree(int x, int y): l(x), r(y){
		if(l==r) return;
		left = new segtree(l,mid);
		right = new segtree(mid+1,r);
	}
	void updateX(int x, int y){
		if(x<l || r<x) return;
		if(x==l && r==x){
			X=y;
			return;
		}
		left->updateX(x,y);
		right->updateX(x,y);
		X=((left->X)*(right->X))%mod;
	}
	void updateY(int x, int y){
		if(x<l || r<x) return;
		if(x==l && r==x){
			Y=y;
			return;
		}
		left->updateY(x,y);
		right->updateY(x,y);
		Y=max(left->Y,right->Y);
	}
	ll queryX(int x, int y){
		if(y<l || r<x) return 1;
		if(x<=l && r<=y) return X;
		return (left->queryX(x,y))*(right->queryX(x,y))%mod;
	}
	ll queryY(int x, int y){
		if(y<l || r<x) return 0;
		if(x<=l && r<=y) return Y;
		return max(left->queryY(x,y),right->queryY(x,y));
	}
} st(0,N);

set<int> p;
ll A[N], B[N], n;

int solve(){
	auto it=p.rbegin();
	vector<pii> segs;
	segs.pb({n,0});
	ll mul=1, mx=0, px, ax=1;
	while(it!=p.rend() && mul<=1e9){
		mul*=A[*it];
		segs.pb({*it,0});
		it++;
	}
	if(segs.back().fi>0 && mul<=1e9) segs.pb({0,0});
	reverse(all(segs));
	px=st.queryX(0,segs[0].fi);
	rep(i,0,segs.size()-1) segs[i].se=st.queryY(segs[i].fi,segs[i+1].fi-1);
	mx=segs[0].se;
	rep(i,1,segs.size()-1){
		ax*=A[segs[i].fi];
		mx=max(mx,ax*segs[i].se);
	}
	return (px*(mx%mod))%mod;
}

int init(int N, int X[], int Y[]){
	rep(i,0,N){
		st.updateX(i,X[i]);
		st.updateY(i,Y[i]);
		if(X[i]>1) p.insert(i);
		A[i]=X[i];
		B[i]=Y[i];
	}
	n=N;
	return solve();
}

int updateX(int pos, int val) {
	st.updateX(pos,val);
	if(A[pos]>1) p.erase(pos);
	A[pos]=val;
	if(A[pos]>1) p.insert(pos);
	return solve();
}

int updateY(int pos, int val) {
	st.updateY(pos,val);
	return solve();
}

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