Submission #387163

#	Time	Username	Problem	Language	Result	Execution time	Memory
387163		Keshi	Horses (IOI15_horses)	C++17	100 / 100	469 ms	53104 KiB

horses

//In the name of God
#include <bits/stdc++.h>
#include "horses.h"
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

const ll maxn = 5e5 + 100;
const ll mod = 1e9 + 7;
const ll inf = 1e18;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()
#define lc (id << 1)
#define rc (id << 1 | 1)

ll n, x[maxn], y[maxn];
pll seg[maxn << 2];

void bld(ll id, ll s, ll e, ll f = -1){
	if(f != -1 && (f < s || e <= f)) return;
	if(e - s == 1){
		seg[id] = Mp(x[s], x[s] * y[s]);
		return;
	}
	ll mid = (s + e) >> 1;
	bld(lc, s, mid, f);
	bld(rc, mid, e, f);
	seg[id] = Mp(seg[lc].F * seg[rc].F % mod, max(seg[lc].S, seg[lc].F * seg[rc].S));
	return;
}

pll get(ll id, ll s, ll e, ll l, ll r){
	if(r <= s || e <= l) return Mp(1, 0);
	if(l <= s && e <= r) return seg[id];
	ll mid = (s + e) >> 1;
	pll p1 = get(lc, s, mid, l, r);
	pll p2 = get(rc, mid, e, l, r);
	return Mp(p1.F * p2.F % mod, max(p1.S, p1.F * p2.S));
}

set<ll> st;

int solve(){
	auto it = st.begin();
	ll p = 1;
	ll r = -1;
	while(it != st.end()){
		p *= x[-*it];
		if(p >= mod){
			r = -*it;
			break;
		}
		it++;
	}
	pll c = get(1, 0, n, r + 1, n);
	if(r != -1) c.S = max(c.S, y[r]);
	c.S %= mod;
	pll d = get(1, 0, n, 0, r + 1);
	return d.F * c.S % mod;
}

int init(int N, int X[], int Y[]) {
	n = N;
	for(ll i = 0; i < n; i++){
		x[i] = X[i];
		y[i] = Y[i];
		if(x[i] > 1){
			st.insert(-i);
		}
	}
	bld(1, 0, n);
	return solve();
}

int updateX(int pos, int val){
	if(x[pos] > 1) st.erase(-pos);
	x[pos] = val;
	if(x[pos] > 1) st.insert(-pos);
	bld(1, 0, n, pos);
	return solve();
}

int updateY(int pos, int val){
	y[pos] = val;
	bld(1, 0, n, pos);
	return solve();
}

/*int main(){
    fast_io;



    return 0;
}*/

Compilation message (stderr)

horses.cpp: In function 'int solve()':
horses.cpp:67:19: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   67 |  return d.F * c.S % mod;
      |         ~~~~~~~~~~^~~~~

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