Submission #1294536

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294536		blackscreen1	Horses (IOI15_horses)	C++20	100 / 100	364 ms	99264 KiB

horses

#include "horses.h"
#include <bits//stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_multiset;
#define ll long long
#define ld long double
#define iloop(m, h) for (ll i = m; i != h; i += (m < h ? 1 : -1))
#define jloop(m, h) for (auto j = m; j != h; j += (m < h ? 1 : -1))
#define kloop(m, h) for (auto k = m; k != h; k += (m < h ? 1 : -1))
#define lloop(m, h) for (auto l = m; l != h; l += (m < h ? 1 : -1))
#define iloop_(m, h, g) for (auto i = m; i != h; i += g)
#define jloop_(m, h, g) for (auto j = m; j != h; j += g)
#define kloop_(m, h, g) for (auto k = m; k != h; k += g)
#define lloop_(m, h, g) for (auto l = m; l != h; l += g)
#define getchar_unlocked _getchar_nolock // comment before submission
#define pll pair<ll, ll>
#define plll pair<ll, pll>
#define pllll pair<pll, pll>
#define vll vector<ll>
#define qll queue<ll>
#define dll deque<ll>
#define pqll priority_queue<ll>
#define gll greater<ll>
#define INF 1000000000000000
#define MOD1 1000000007
#define MOD2 998244353
#define MOD3 1000000009
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
set<ll> st;
ll n, x[500005], y[500005];
struct node {
	ll s, e, m, px, mxy;
	node *l, *r;
	node (ll S, ll E) {
		s = S, e = E, m = (S+E)>>1;
		if (s == e) {
			mxy = y[s];
			px = x[s];
			if (x[s] != 1) st.insert(s);
			return;
		}
		l = new node(s, m);
		r = new node(m+1, e);
		px = (l->px * r->px)%MOD1;
		mxy = max(l->mxy, r->mxy);
	}
	void updx(ll X, ll V) {
		if (s == e) {px = V; return;}
		if (X <= m) l->updx(X, V);
		else r->updx(X, V);
		px = (l->px * r->px)%MOD1;
	}
	void updy(ll X, ll V) {
		if (s == e) {mxy = V; return;}
		if (X <= m) l->updy(X, V);
		else r->updy(X, V);
		mxy = max(l->mxy, r->mxy);
	}
	ll qux(ll S, ll E) {
		if (S > E) return 1;
		if (s == S && e == E) return px;
		if (E <= m) return l->qux(S, E);
		if (S > m) return r->qux(S, E);
		return (l->qux(S, m) * r->qux(m+1, E))%MOD1;
	}
	ll quy(ll S, ll E) {
		if (S > E) return 1;
		if (s == S && e == E) return mxy;
		if (E <= m) return l->quy(S, E);
		if (S > m) return r->quy(S, E);
		return max(l->quy(S, m), r->quy(m+1, E));
	}
} *root;
ll calc() {
	if (!st.size()) return root->quy(0, n-1);
	auto it = --st.end();
	ll cpd = x[*it];
	while (cpd <= 1e9 && it != st.begin()) {
		it--;
		cpd *= x[*it];
	}
	ll cans = 1, cprod = 1, cf = 1;
	if (cpd > 1e9) {
		cpd /= x[*it]; 
		cans = root->quy(*it, n-1);
		it++;
	}
	if (it == st.begin()) {
		cans = root->quy(0, *it-1);
	}
	cf = root->qux(0, *it - 1);
	while (it != st.end()) {
		cprod *= x[*it];
		cans = max(cans, cprod * root->quy(*it, n-1));
		it++;
	}
	return ((cans%MOD1)*cf)%MOD1;
}
int init(int N, int X[], int Y[]) {
	n = N;
	iloop(0, n) x[i] = X[i], y[i] = Y[i];
	root = new node(0, n-1);
	return calc();
}

int updateX(int pos, int val) {	
	if (x[pos] != 1) st.erase(pos);
	x[pos] = val;
	root->updx(pos, val);
	if (x[pos] != 1) st.insert(pos);
	return calc();
}

int updateY(int pos, int val) {
	root->updy(pos, val);
	return calc();
}

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