Submission #16723

#	Time	Username	Problem	Language	Result	Execution time	Memory
16723		comet	말 (IOI15_horses)	C++98	0 / 100	289 ms	53324 KiB

horses

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include "horses.h"
using namespace std;
#define MOD (ll)(1e9+7)
typedef long long ll;
ll N,X[500001],Y[500001];
struct SegTree{
	struct node{
		ll L,R,E,p;
		node(){L=R=E=1;p=500000;}
		node(int x,int v){
			L=E=x;
			R=1;
			p=v;
		}
	};
	vector<node> tree;
	int sz;
	void init(int n){
		for(sz=1;sz<n;sz<<=1);
		sz--;
		tree.resize(n+sz+1,node());
	}
	#define LL (x<<1)
	#define RR ((x<<1)+1)
	void update(int pos,int val){
		int x=pos+sz;
		tree[x]=node(val,pos);
		x>>=1;
		while(x){
			ll z=tree[LL].R*tree[RR].L;
			if(z>MOD)z=MOD;
			if(z*Y[tree[RR].p]>Y[tree[LL].p]){
				tree[x].p=tree[RR].p;
				tree[x].L=min(MOD,tree[LL].E*tree[RR].L);
				tree[x].R=tree[RR].R;
				tree[x].E=min(MOD,tree[LL].E*tree[RR].E);
			}
			else{
				tree[x].p=tree[LL].p;
				tree[x].L=tree[LL].L;
				tree[x].R=min(MOD,tree[LL].R*tree[RR].E);
				tree[x].E=min(MOD,tree[LL].E*tree[RR].E);
			}
			x>>=1;
		}
	}
	int query(){
		return tree[1].p;
	}
	#undef LL
	#undef RR
}horse;
struct MUL{
	vector<ll> tree;
	int sz;
	void init(int n){
		for(sz=1;sz<n;sz<<=1);
		sz--;
		tree.resize(sz+n+1,1);
	}
	void update(int x,int c){
		x+=sz;
		tree[x]=c;
		x>>=1;
		while(x){
			tree[x]=(tree[x*2]*tree[x*2+1])%MOD;
			x>>=1;
		}
	}
	ll query(int L,int R){
		L+=sz,R+=sz;
		ll ret=1;
		while(L<R){
			if(L&1)ret=(ret*tree[L++])%MOD;
			if(~R&1)ret=(ret*tree[R--])%MOD;
			L>>=1,R>>=1;
		}
		if(L==R)ret=(ret*tree[L])%MOD;
		return ret;
	}
}mul;
int init(int n, int x[], int y[]) {
	N=n;
	horse.init(n);
	mul.init(n);
	for(int i=0;i<n;i++){
		X[i+1]=x[i];
		Y[i+1]=y[i];
		horse.update(i+1,x[i]);
		mul.update(i+1,x[i]);
	}
}

int updateX(int pos, int val) {
	pos++;
	X[pos]=val;
	horse.update(pos,val);
	return mul.query(1,horse.query());
}

int updateY(int pos, int val) {
	pos++;
	Y[pos]=val;
	horse.update(pos,val);
	return mul.query(1,horse.query());
}

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