Submission #599108

#	Time	Username	Problem	Language	Result	Execution time	Memory
599108		sofapuden	Horses (IOI15_horses)	C++14	100 / 100	563 ms	144524 KiB

horses

#include <bits/stdc++.h>
#include "horses.h"

using namespace std;

typedef long long ll;

const ll M = 1e9+7;

struct seg2 {
	struct nod {
		ll val;
		ll val2;
	};
	int n;
	vector<nod> st;
	vector<ll> A;

	seg2() {}
	seg2(int sz) : n(sz), st(4*n) {}
	seg2(vector<ll> &in) : seg2((int)in.size()) {
		A = in;
		build(0,n-1,1);
	}

	nod merge (nod a, nod b) {
		nod c;
		c.val = min(1ll<<30,a.val*b.val);
		c.val2 = a.val2*b.val2%M;
		return c;
	}
	
	void build(int l, int r, int p){
		if(l == r){
			nod c;
			c.val = A[l];
			c.val2 = A[l];
			st[p] = c;
			return;
		}
		int m = (l+r) >> 1;
		build(l,m,p<<1);
		build(m+1,r,p<<1|1);
		st[p] = merge(st[p<<1],st[p<<1|1]);
	}

	void update(int x, ll val, int l, int r, int p){
		if(l == r){
			nod c;
			c.val = val;
			c.val2 = val;
			st[p] = c;
			return;
		}
		int m = (l+r) >> 1;
		if(m >= x)update(x,val,l,m,p<<1);
		else update(x,val,m+1,r,p<<1|1);
		st[p] = merge(st[p<<1], st[p<<1|1]);
	}
	void updateno(int x, int l, int r, int p){
		if(l == r){
			return;
		}
		int m = (l+r) >> 1;
		if(m >= x)updateno(x,l,m,p<<1);
		else updateno(x,m+1,r,p<<1|1);
		st[p] = merge(st[p<<1], st[p<<1|1]);
	}

	nod que(int i, int j, int l, int r, int p){
		if(l >= i && r <= j)return st[p];
		int m = (l+r)>>1;
		if(m < i)return que(i,j,m+1,r,p<<1|1);
		else if(m >= j)return que(i,j,l,m,p<<1);
		else return merge(que(i,j,l,m,p<<1),que(i,j,m+1,r,p<<1|1));
	}
}st2;

struct seg {
	struct nod {
		int pos;
	};
	int n;
	vector<nod> st;
	vector<ll> Ax;
	vector<ll> Ay;
	seg2 stval;

	seg() {}
	seg(int sz) : n(sz), st(4*n) {}
	seg(vector<ll> &_X, vector<ll> &_Y, seg2 _stval) : seg((int)_X.size()) {
		Ax = _X;
		Ay = _Y;
		stval = _stval;
		build(0,n-1,1);
	}

	nod merge (nod a, nod b) {
		ll v1 = stval.que(a.pos+1,b.pos,0,n-1,1).val*Ay[b.pos];
		ll v2 = Ay[a.pos];
		if(v1 > v2)return b;
		else return a;
	}
	
	void build(int l, int r, int p){
		if(l == r){
			nod c;
			c.pos = l;
			st[p] = c;
			return;
		}
		int m = (l+r) >> 1;
		build(l,m,p<<1);
		build(m+1,r,p<<1|1);
		st[p] = merge(st[p<<1],st[p<<1|1]);
	}

	void update(int x, ll val, int l, int r, int p){
		if(l == r){
			Ay[l] = val;
			return;
		}
		int m = (l+r) >> 1;
		if(m >= x)update(x,val,l,m,p<<1);
		else update(x,val,m+1,r,p<<1|1);
		st[p] = merge(st[p<<1], st[p<<1|1]);
	}
	void updateno(int x, int l, int r, int p){
		if(l == r){
			return;
		}
		int m = (l+r) >> 1;
		if(m >= x)updateno(x,l,m,p<<1);
		else updateno(x,m+1,r,p<<1|1);
		st[p] = merge(st[p<<1], st[p<<1|1]);
	}

	nod que(int i, int j, int l, int r, int p){
		if(l >= i && r <= j)return st[p];
		int m = (l+r)>>1;
		if(m < i)return que(i,j,m+1,r,p<<1|1);
		else if(m >= j)return que(i,j,l,m,p<<1);
		else return merge(que(i,j,l,m,p<<1),que(i,j,m+1,r,p<<1|1));
	}
}st;

int glN;
vector<ll> x, y;

int init(int N, int X[], int Y[]) {
	glN = N;
	x.resize(N);
	y.resize(N);
	for(int i = 0; i < N; ++i){
		x[i] = X[i];
		y[i] = Y[i];
	}
	st2 = seg2(x);
	st = seg(x,y,st2);
	return (int)(st.stval.que(0,st.st[1].pos,0,glN-1,1).val2*y[st.st[1].pos]%M);
}

int updateX(int pos, int val) {	
	x[pos] = val;
	st.stval.update(pos,val,0,glN-1,1);
	st.updateno(pos,0,glN-1,1);
	return (int)(st.stval.que(0,st.st[1].pos,0,glN-1,1).val2*y[st.st[1].pos]%M);
}

int updateY(int pos, int val) {
	y[pos] = val;
	st.update(pos,val,0,glN-1,1);
	st.stval.updateno(pos,0,glN-1,1);
	return (int)(st.stval.que(0,st.st[1].pos,0,glN-1,1).val2*y[st.st[1].pos]%M);
}

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