Submission #823424

#	Time	Username	Problem	Language	Result	Execution time	Memory
823424		_martynas	Horses (IOI15_horses)	C++11	20 / 100	379 ms	49316 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#warning change mxn
const int mxn = 5e5+5;
const int mxval = 1e9;
const int mod = 1e9+7;

struct Seg {
	int mx[4*mxn];
	int get(int u, int l, int r, int ql, int qr) {
		if(qr < l || r < ql) return 0;
		if(ql <= l && r <= qr) return mx[u];
		int m = (l+r)/2;
		return max(get(2*u, l, m, ql, qr), get(2*u+1, m+1, r, ql, qr));
	}
	void set(int u, int l, int r, int i, int x) {
		if(l == r) {
			mx[u] = x; return;
		}
		int m = (l+r)/2;
		if(i <= m) set(2*u, l, m, i, x);
		else set(2*u+1, m+1, r, i, x);
		mx[u] = max(mx[2*u], mx[2*u+1]);
	}
} seg;
int n;
int x[mxn], y[mxn];
set<int> st;
ll tot = 1;

ll mod_pow(ll a, ll b) {
	ll ans = 1;
	while(b) {
		if(b & 1) ans = ans*a%mod;
		a = a*a%mod;
		b >>= 1;
	}
	return ans;
}

int get();
int init(int N, int X[], int Y[]) {
	n = N;
	copy(X, X+n, x); copy(Y, Y+n, y);
	for(int i = 0; i < N; i++) seg.set(1, 0, n-1, i, Y[i]);
	st.insert(n);
	for(int i = n-1; i >= 0; i--) {
		if(X[i] > 1) {
			tot = tot*X[i]%mod;
			st.insert(i);
		}
	}
	return get();
}

int get() {
	ll acc = 1;
	int last = -1;
	auto rit = next(st.rbegin());
	while(rit != st.rend()) {
		acc *= x[*rit];
		last = *rit;
		if(acc > mxval) break;
		rit = next(rit);
	}
	auto it = st.lower_bound(last);
	ll mx = 0; acc = 1;
	while(next(it) != st.end()) {
		int i = *it;
		int j = *next(it);
		if(i != last) acc = acc*x[i];
		ll best_y = seg.get(1, 0, n-1, i, j-1);
		mx = max(mx, acc*best_y);
		it = next(it);
	}
	//printf("mx = %lld\n", mx);
	mx %= mod;
	return tot*mod_pow(acc, mod-2)%mod*mx%mod;
}

int updateX(int pos, int val) {
	tot = tot*mod_pow(x[pos], mod-2)%mod;
	x[pos] = val;
	tot = tot*val%mod;
	if(val > 1) st.insert(pos);
	else (st.erase(pos));
	return get();
}

int updateY(int pos, int val) {
	seg.set(1, 0, n-1, pos, val);
	return get();
}

// int main(int argc, char const *argv[])
// {
// 	int N;
// 	cin >> N;
// 	int X[N], Y[N];
// 	for(int i = 0; i < N; i++) cin >> X[i];
// 	for(int i = 0; i < N; i++) cin >> Y[i];
// 	cout << "init: " << init(N, X, Y) << "\n";
// 	int M;
// 	cin >> M;
// 	for(int i = 0; i < M; i++) {
// 		int type; cin >> type;
// 		int pos, val; cin >> pos >> val;
// 		if(type == 1) {
// 			cout << "resp: " << updateX(pos, val) << "\n";
// 		}
// 		else {
// 			cout << "resp: " << updateY(pos, val) << "\n";
// 		}
// 	}
// 	return 0;
// }

Compilation message (stderr)

horses.cpp:8:2: warning: #warning change mxn [-Wcpp]
    8 | #warning change mxn
      |  ^~~~~~~
horses.cpp: In function 'int get()':
horses.cpp:83:39: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   83 |  return tot*mod_pow(acc, mod-2)%mod*mx%mod;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

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