Submission #64658

#	Time	Username	Problem	Language	Result	Execution time	Memory
64658		FLDutchman	Horses (IOI15_horses)	C++14	20 / 100	657 ms	57396 KiB

horses

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

typedef int INT;

#define int long long
#define FOR(i, l, r) for(int i = (l); i < (r); i++)
#define pb push_back
#define fst first
#define snd second
#define LSB(k) k&-k

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;

const int mod = 1e9+7;

struct segtree{
	vi t;
	segtree(int N){
		t.assign(4*N, 0);
	}	

	segtree(){}

	void update(int n){
		t[n] = max(t[n<<1], t[n<<1|1]);
	}

	void modify(int i, int v, int lb, int rb, int n = 1){
		if(lb + 1 == rb) {
			t[n] = v;
			return;
		}
		int mb = (lb+rb)/2;
		if(i < mb) modify(i, v, lb, mb, n<<1);
		else modify(i, v, mb, rb, n<<1|1);
		update(n);
	}

	int rmq(int l, int r, int lb, int rb, int n = 1){
		if(lb <= l and r <= rb) return t[n];
		int mb = (lb + rb)/2;
		int res = 0;
		if(l < mb) res = max(res, rmq(l, r, lb, mb, n<<1));
		if (r > mb) res = max(res, rmq(l, r, mb, rb, n<<1|1));
		return res;
	}
};

int mpow(int a, int b){
	if(b == 0) return 1;
	if(b == 1) return a;
	if(b & 1) return a * mpow(a*a%mod, b>>1) % mod;
	return mpow(a*a%mod, b>>1);
}

int N;
vi X, Xinv, Y;
segtree tree;
multiset<int> nonunit;
int prod;
vi prev, range;

int getBest(){
	//cout << prod << endl;
	int i = N-1;
	int y = Y[i];
	int p = prod;
	while(y < mod && i > 0){
		if(X[i] == 1) {
			// precompute it and rmq?
			auto it = --nonunit.lower_bound(i);
			y = max(y*X[i],  tree.rmq(*it+1, i+1, 0, N));
			i = *it;
		} else {
			p = p * Xinv[i] % mod;
			y = max(y * X[i], Y[i-1]);
			i--;
		}

	}
	y %= mod;
	//cout << p << " " << y << endl;
	return p * y % mod;
}

INT init(INT n, INT x[], INT y[]) {
	N = n;
	tree = segtree(N);
	prod = 1;
	nonunit.insert(-1);
	FOR(i, 0, N) Y.pb(y[i]), X.pb(x[i]), tree.modify(i, y[i], 0, N), Xinv.pb(mpow(x[i], mod-2)), prod = prod * X[i] % mod;
	FOR(i, 0, N) if(X[i] != 1) nonunit.insert(i);
	return getBest();
}

//void rem(int i){
//	nonunit.erase(i);
//
//}

INT updateX(INT pos, INT val) {	
	if(X[pos] != 1) nonunit.erase(pos);
	prod = prod * Xinv[pos] % mod * val % mod;
	X[pos] = val;
	Xinv[pos] = mpow(val, mod-2);
	if(val != 1) nonunit.insert(pos);



	return getBest();
}

INT updateY(INT pos, INT val) {
	Y[pos] = val;
	tree.modify(pos, val, 0, N);
	return getBest();
}

Compilation message (stderr)

horses.cpp: In function 'INT init(INT, INT*, INT*)':
horses.cpp:97:16: warning: conversion to 'INT {aka int}' from 'long long int' may alter its value [-Wconversion]
  return getBest();
         ~~~~~~~^~
horses.cpp: In function 'INT updateX(INT, INT)':
horses.cpp:114:16: warning: conversion to 'INT {aka int}' from 'long long int' may alter its value [-Wconversion]
  return getBest();
         ~~~~~~~^~
horses.cpp: In function 'INT updateY(INT, INT)':
horses.cpp:120:16: warning: conversion to 'INT {aka int}' from 'long long int' may alter its value [-Wconversion]
  return getBest();
         ~~~~~~~^~

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