Submission #1162790

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162790		kl0989e	Horses (IOI15_horses)	C++20	17 / 100	1168 ms	134648 KiB

horses

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

#define ll long long
#define pi pair<int, int>
#define pl pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()

const int mod=1e9+7;

ll pw(ll a, ll pww) {
	if (pww==0) {
		return 1;
	}
	ll temp=pw(a,pww>>1);
	temp=(temp*temp)%mod;
	if (pww&1) {
		temp=(temp*a)%mod;
	}
	return temp;
}

ll inv(ll a) {
	return pw(a,mod-2);
}

struct node {
	long double val=0;
	ll ret=1;

	long double lzyval=0;
	int lzyret=1;
};

const int maxn=5e5+10;

int n;
vector<node> nodes(maxn*4);
vi x(maxn);
vi y(maxn);

node merge(node a, node b) {
	if (a.val>=b.val) {
		return a;
	}
	return b;
}
void push(int v, int tl, int tr) {
	nodes[v].val+=nodes[v].lzyval;
	nodes[v].ret=(nodes[v].ret*nodes[v].lzyret)%mod;
	if (tl!=tr) {
		nodes[2*v].lzyval+=nodes[v].lzyval;
		nodes[2*v].lzyret=(nodes[2*v].lzyret*nodes[v].lzyret)%mod;
		nodes[2*v+1].lzyval+=nodes[v].lzyval;
		nodes[2*v+1].lzyret=(nodes[2*v+1].lzyret*nodes[v].lzyret)%mod;
	}
	nodes[v].lzyval=0;
	nodes[v].lzyret=1;
}

void update(int l, int r, long double val, ll ret, int v=1, int tl=0, int tr=n-1) {
	push(v,tl,tr);
	if (l<=tl && tr<=r) {
		nodes[v].lzyval+=val;
		nodes[v].lzyret=(nodes[v].lzyret*ret)%mod;
		push(v,tl,tr);
		return;
	}
	if (tr<l || r<tl) {
		return;
	}
	int tm=tl+(tr-tl)/2;
	update(l,r,val,ret,2*v,tl,tm);
	update(l,r,val,ret,2*v+1,tm+1,tr);
	nodes[v]=merge(nodes[2*v],nodes[2*v+1]);
}

int init(int _n, int X[], int Y[]) {
	n=_n;
	for (int i=0; i<n; i++) {
		x[i]=X[i];
		update(i,n-1,log(x[i]),x[i]);
		y[i]=Y[i];
		update(i,i,log(y[i]),y[i]);
	}
	return nodes[1].ret;
}

int updateX(int pos, int val) {
	update(pos,n-1,log(val)-log(x[pos]),val*inv(x[pos])%mod);
	return nodes[1].ret;
}

int updateY(int pos, int val) {
	update(pos,pos,log(val)-log(y[pos]),val*inv(y[pos])%mod);
	return nodes[1].ret;
}

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