Submission #1135805

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135805		gyg	Horses (IOI15_horses)	C++20	100 / 100	1020 ms	69112 KiB

horses

// 0 indexed btw

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define lint long long
#define arr array 
#define pli pair<lint, int>
#define pii pair<int, int>
#define fir first 
#define sec second
#define vec vector 
const int N = 5e5 + 5, INF = 2e9;
const lint MD = 1e9 + 7;

int n;
arr<lint, N> grw, prc;

lint md(lint x) { return (x + MD) % MD; }
struct Prd_Sg {
	arr<lint, 5 * N> sg;
	void bld(int u = 1, int lw = 1, int hg = n) {
		if (lw == hg) { sg[u] = grw[lw]; return; }
		int mdl = (lw + hg) / 2;
		bld(2 * u, lw, mdl), bld(2 * u + 1, mdl + 1, hg);
		sg[u] = md(sg[2 * u] * sg[2 * u + 1]);
	}
	void upd(int i, lint x, int u = 1, int lw = 1, int hg = n) {
		if (i < lw || hg < i) return;
		if (lw == hg) { sg[u] = x; return; }
		int mdl = (lw + hg) / 2;
		upd(i, x, 2 * u, lw, mdl), upd(i, x, 2 * u + 1, mdl + 1, hg);
		sg[u] = md(sg[2 * u] * sg[2 * u + 1]);
	}
	lint qry(int l, int r, int u = 1, int lw = 1, int hg = n) {
		if (r < lw || hg < l) return 1;
		if (l <= lw && hg <= r) return sg[u];
		int mdl = (lw + hg) / 2;
		return md(qry(l, r, 2 * u, lw, mdl) * qry(l, r, 2 * u + 1, mdl + 1, hg));
	}
} prd_sg;

set<pair<pii, lint>> rng;

struct Mx_Sg {
	arr<pli, 5 * N> sg;
	void bld(int u = 1, int lw = 1, int hg = n) {
		if (lw == hg) { sg[u] = {prc[lw], lw}; return; }
		int md = (lw + hg) / 2;
		bld(2 * u, lw, md), bld(2 * u + 1, md + 1, hg);
		sg[u] = max(sg[2 * u], sg[2 * u + 1]);
	}
	void upd(int i, int x, int u = 1, int lw = 1, int hg = n) {
		if (i < lw || hg < i) return;
		if (lw == hg) { sg[u] = {x, lw}; return; }
		int md = (lw + hg) / 2;
		upd(i, x, 2 * u, lw, md), upd(i, x, 2 * u + 1, md + 1, hg);
		sg[u] = max(sg[2 * u], sg[2 * u + 1]);
	}
	pli qry(int l, int r, int u = 1, int lw = 1, int hg = n) {
		if (r < lw || hg < l) return {-1, -1};
		if (l <= lw && hg <= r) return sg[u];
		int md = (lw + hg) / 2;
		return max(qry(l, r, 2 * u, lw, md), qry(l, r, 2 * u + 1, md + 1, hg));
	}
} mx_sg;

vec<pair<pii, lint>> sf;
lint slv() {
	sf.clear();
	int cnt = 0;
	for (auto it = rng.rbegin(); it != rng.rend() && cnt <= 64; it++, cnt++) sf.push_back(*it);
	reverse(sf.begin(), sf.end());

	int bst = 0;
	lint grw_prd = 1;
	for (pair<pii, lint> x : sf) {
		grw_prd *= x.sec;
		if (grw_prd > prc[bst] || grw_prd * mx_sg.qry(x.fir.fir, x.fir.sec).fir > prc[bst]) {
			bst = mx_sg.qry(x.fir.fir, x.fir.sec).sec;
			grw_prd = 1;
		}
	}
	assert(bst != 0);

	lint ans = md(prd_sg.qry(1, bst) * prc[bst]);
	return ans;
}

int init(int _n, int _grw[], int _prc[]) {
	n = _n;
	for (int i = 1; i <= n; i++) grw[i] = _grw[i - 1], prc[i] = _prc[i - 1];
	
	prd_sg.bld(), mx_sg.bld();
	rng.clear();
	for (int i = 1; i <= n; i++) {
		if (rng.size() && rng.rbegin()->sec == 1 && grw[i] == 1) {
			pii x = rng.rbegin()->fir;
			rng.erase(--rng.end());
			rng.insert({{x.fir, i}, 1});
		} else rng.insert({{i, i}, grw[i]});
	}

	// for (pair<pii, lint> x : rng) cout << x.fir.fir << " " << x.fir.sec << ": " << x.sec << endl;

	return slv();
}

int updateX(int id, int vl) {	
	id++;

	if (grw[id] != 1 && vl != 1) {
		rng.erase({{id, id}, grw[id]});
		rng.insert({{id, id}, vl});
	} else if (grw[id] != 1 && vl == 1) {
		rng.erase({{id, id}, grw[id]});
		rng.insert({{id, id}, vl});
		
		auto it = rng.find({{id, id}, vl});
		if (it != rng.begin() && next(it, -1)->sec == 1) {
			pair<pii, lint> x = *it, y = *next(it, -1);
			rng.erase(x), rng.erase(y);
			it = rng.insert({{y.fir.fir, x.fir.sec}, 1}).fir;
		} 
		if (next(it, 1) != rng.end() && next(it, 1)->sec == 1) {
			pair<pii, lint> x = *it, y = *next(it, 1);
			rng.erase(x), rng.erase(y);
			it = rng.insert({{x.fir.fir, y.fir.sec}, 1}).fir;
		}
	} else if (grw[id] == 1 && vl != 1) {
		auto it = --rng.upper_bound({{id, INF}, INF});
		if (it->fir.fir != id) {
			pair<pii, lint> x = *it;
			rng.erase(it);
			rng.insert({{x.fir.fir, id - 1}, 1});
			it = rng.insert({{id, x.fir.sec}, 1}).fir;
		}
		if (it->fir.sec != id) {
			pair<pii, lint> x = *it;
			rng.erase(it);
			rng.insert({{id + 1, x.fir.sec}, 1});
			it = rng.insert({{x.fir.fir, id}, 1}).fir;
		}

		rng.erase({{id, id}, grw[id]});
		rng.insert({{id, id}, vl});
	} else assert(grw[id] == 1 && vl == 1);

	
	// for (pair<pii, lint> x : rng) cout << x.fir.fir << " " << x.fir.sec << ": " << x.sec << endl;
	
	grw[id] = vl, prd_sg.upd(id, vl);
	return slv();
}

int updateY(int id, int vl) {
	id++;
	prc[id] = vl, mx_sg.upd(id, vl);
	return slv();
}

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