oj.uz

Submission #16725

# Submission time Handle Problem Language Result Execution time Memory
16725 2015-09-10T06:04:24 Z comet Horses (IOI15_horses) C++
0 / 100
 279 ms 54280 KB 
#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[500010],Y[500010];
struct SegTree{
	struct node{
		ll L,R,E,p;
		node(){L=R=E=1;p=500001;}
		node(int pos,int val){
			L=E=val;
			R=1;
			p=pos;
		}

		void write(){
			printf("%lld %lld %lld %lld",p,L,R,E);
		}
	};
	vector<node> tree;
	int sz;
	void init(int n){
		for(sz=1;sz<n;sz<<=1);
		sz--;
		tree.resize(2*sz+10);
	}

	#define LL (x<<1)
	#define RR ((x<<1)+1)
	void update(int pos,int val){
		int x=pos+sz;
		tree[x]=node(pos,val);
		x>>=1;
		while(x){
			ll z=min(MOD,tree[LL].R*tree[RR].L);
/*
			printf("x=%d\n",x);
			printf("L-> ");tree[LL].write();puts("");
			printf("R-> ");tree[RR].write();puts("");
*/
			if(Y[tree[LL].p]<z*Y[tree[RR].p]){
				//puts("1");
				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{
				//puts("2");
				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(2*sz+10,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];
	}
	for(int i=1;i<=n;i++)horse.update(i,X[i]),mul.update(i,X[i]);
	//printf("pos=%d\n",horse.query());
	ll ret=mul.query(1,horse.query());
	ret=(ret*Y[horse.query()])%MOD;
}

int updateX(int pos, int val) {
	pos++;
	X[pos]=val;
	horse.update(pos,val);
	mul.update(pos,val);
	//printf("updateX : pos=%d\n",horse.query());
	ll ret=mul.query(1,horse.query());
	ret=(ret*Y[horse.query()])%MOD;
	return ret;
}

int updateY(int pos, int val) {
	pos++;
	Y[pos]=val;
	horse.update(pos,X[pos]);
	//printf("updateY : pos=%d\n",horse.query());
	ll ret=mul.query(1,horse.query());
	ret=(ret*Y[horse.query()])%MOD;
	return ret;
}

Subtask #1
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 9400 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 9400 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 279 ms 54280 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 9400 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 9400 KB Output isn't correct
2 Halted 0 ms 0 KB -