Submission #730121

#	Time	Username	Problem	Language	Result	Execution time	Memory
730121		sentheta	Horses (IOI15_horses)	C++17	37 / 100	549 ms	53028 KiB

horses

#include "horses.h"
// author : sentheta aka vanwij
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cassert>
#include<random>
#include<chrono>
#include<cmath>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define dbg(x) if(1) cout << "?" << #x << " : " << (x) << endl << flush;

const Int MOD = 1e9+7;
const int N = 5e5+5;

int n;
int *x, *y;

#define mid (tl+tr)/2
#define lc (v+1)
#define rc (v+2*(mid-tl+1))
struct Maxsegtree{
	int mx[2*N];
	void upd(int i,int val,int v=0,int tl=0,int tr=n-1){
		if(tl==tr){
			mx[v] = val; return;
		}
		if(i<=mid) upd(i,val, lc,tl,mid);
		else upd(i,val, rc,mid+1,tr);
		mx[v] = max(mx[lc], mx[rc]);
	}
	int qry(int l,int r,int v=0,int tl=0,int tr=n-1){
		if(r<tl || tr<l) return 0;
		if(l<=tl && tr<=r) return mx[v];
		return max(qry(l,r, lc,tl,mid), qry(l,r, rc,mid+1,tr));
	}
} maxtree;
struct Mulsegtree{
	Int prod[2*N];
	void upd(int i,Int val,int v=0,int tl=0,int tr=n-1){
		if(tl==tr){
			prod[v] = val; return;
		}
		if(i<=mid) upd(i,val, lc,tl,mid);
		else upd(i,val, rc,mid+1,tr);
		prod[v] = prod[lc] * prod[rc] % MOD;
	}
	Int qry(int l,int r,int v=0,int tl=0,int tr=n-1){
		if(r<tl || tr<l) return 1;
		if(l<=tl && tr<=r) return prod[v];
		return qry(l,r, lc,tl,mid) * qry(l,r, rc,mid+1,tr) % MOD;
	}
} multree;
#undef mid

set<int> sx;

int solve(){
	if(sx.empty()){
		return (int)maxtree.qry(0,n-1);
	}

	int r = n-1;
	Int ratio = 1, ans = 0, ansmod = 0;
	for(auto it=sx.end(); it!=sx.begin(); ){
		it = prev(it);
		int l = *it;

		Int mxy = maxtree.qry(l,r);
		// dbg(mxy);
		if(mxy > (Int)ans){
			ans = mxy;
			ansmod = multree.qry(0,l) *mxy%MOD;
		}

		ans *= x[l];
		ratio *= x[l];
		if(ratio > MOD) break;
		r = l-1;
	}

	return (int)ansmod;
}

int init(int _n,int _x[], int _y[]){
	n = _n; x = _x; y = _y;

	rep(i,0,n){
		maxtree.upd(i,y[i]);

		multree.upd(i,x[i]);
		if(x[i]!=1) sx.insert(i);
	}

	// dbg(n);
	return solve();
}

int updateX(int i,int val){
	// assert(0);

	if(x[i]!=1) sx.erase(i);
	x[i] = val;
	multree.upd(i,x[i]);
	if(x[i]!=1) sx.insert(i);

	// dbg(n);
	return solve();
}

int updateY(int i,int val){
	// assert(0);

	y[i] = val;
	maxtree.upd(i,y[i]);

	// dbg(n);
	return solve();
}

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