Submission #1277309

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277309		papaulo	Horses (IOI15_horses)	C++20	17 / 100	102 ms	103240 KiB

horses

#include <bits/stdc++.h>
using namespace std;
#include "horses.h"
using ll = long long;

const ll MOD=1e9L+7LL;

int gn=0;

struct Value {
	ll v;
	bool m;
	Value(ll vv, bool mm) : v(vv), m(mm) {}
	Value(ll vv) : Value(vv, false) {}
	Value() : Value(0LL, false) {}
	Value operator*(const Value &o) {
		ll prod=this->v*o.v;
		bool modded=this->m||o.m||prod>=MOD;
		prod%=MOD;
		return Value(prod, modded);
	}
	bool operator>(const Value &o) {
		if(this->m&&!o.m) return true;
		assert(!this->m);
		return this->v>o.v;
	}
};

struct Node {
	Value p1, p2, y;
	Node(int xx, int yy) {
		this->p1=Value(xx);
		this->p2=Value(1);
		this->y=Value(yy);
	}
	Node() {}
	Node operator+(const Node &n) {
		Node ans;
		if(this->y>this->p2*n.p1*n.y) {
			ans.p1=this->p1;
			ans.p2=this->p2*n.p1*n.p2;
			ans.y=this->y;
		} else {
			ans.p1=this->p1*this->p2*n.p1;
			ans.p2=n.p2;
			ans.y=n.y;
		}
		return ans;
	}
};

#define MAXN 500500
int xs[MAXN], ys[MAXN];
Node seg[4*MAXN];

void build(int n, int l, int r) {
	if(l==r) {
		seg[n]=Node(xs[l], ys[l]);
	} else {
		int mid=(l+r)/2;
		build(2*n, l, mid);
		build(2*n+1, mid+1, r);
		seg[n]=seg[2*n]+seg[2*n+1];
	}
}

void update(int n, int l, int r, int i) {
	if(l==r) seg[n]=Node(xs[i], ys[i]);
	else {
		int mid=(l+r)/2;
		if(i<=mid) update(2*n, l, mid, i);
		else update(2*n+1, mid+1, r, i);
		seg[n]=seg[2*n]+seg[2*n+1];
	}
}

int init(int N, int X[], int Y[]) {
	for(int i=0;i<N;i++) xs[i]=X[i];
	for(int i=0;i<N;i++) ys[i]=Y[i];
	build(1, 0, N-1);
	gn=N;
	return (int)((seg[1].p1*seg[1].y).v);
}

int updateX(int pos, int val) {
	xs[pos]=val;
	update(1, 0, gn-1, pos);
	return (int)((seg[1].p1*seg[1].y).v);
}

int updateY(int pos, int val) {
	ys[pos]=val;
	update(1, 0, gn-1, pos);
	return (int)((seg[1].p1*seg[1].y).v);
}

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