제출 #1004976

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1004976		pawned	말 (IOI15_horses)	C++17	100 / 100	346 ms	57428 KiB

horses

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

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

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;

#include "horses.h"

const ll MOD = 1e9 + 7;
const ll MAX = 1e9 + 5;
const ll MAX_SZ = 5e5 + 5;

struct Segtree {	// point update, range max query
	int sz;
	vi vals;
	void init(int N) {
		sz = 1;
		while (sz < N)
			sz *= 2;
		vals = vi(2 * sz, 0);
	}
	void upd(int pos, ll val, int id, int left, int right) {
		if (right - left == 1) {
			vals[id] = val;
			return;
		}
		int mid = (left + right) / 2;
		if (pos < mid)
			upd(pos, val, 2 * id + 1, left, mid);
		else
			upd(pos, val, 2 * id + 2, mid, right);
		vals[id] = max(vals[2 * id + 1], vals[2 * id + 2]);
	}
	void upd(int pos, ll val) {
		upd(pos, val, 0, 0, sz);
	}
	ll query(int qleft, int qright, int id, int left, int right) {
		if (qleft <= left && right <= qright)
			return vals[id];
		if (qright <= left || right <= qleft)
			return 0;
		int mid = (left + right) / 2;
		ll s1 = query(qleft, qright, 2 * id + 1, left, mid);
		ll s2 = query(qleft, qright, 2 * id + 2, mid, right);
		return max(s1, s2);
	}
	ll query(int qleft, int qright) {
		return query(qleft, qright, 0, 0, sz);
	}
};

ll norm(ll x) {
	x %= MOD;
	x += MOD;
	x %= MOD;
	return x;
}

ll binpow(ll x, ll y) {
	x = norm(x);
	ll res = 1;
	while (y > 0) {
		if (y % 2 == 1)
			res = norm(res * x);
		x = norm(x * x);
		y /= 2;
	}
	return res;
}

ll inv(ll x) {
	return binpow(x, MOD - 2);
}

int N;

vi X;
vi Y;

Segtree st;

set<int> gp;	// pos of X w/ val > 1

ll prodall = 1;	// product of all X_i

ll solve() {
	auto it = gp.end();
	ll currn = Y[N - 1];
	ll currd = 1;
	ll bestn = currn;
	ll bestd = currd;
	while (it != gp.begin()) {
		it--;
		if (currd > MAX)
			break;
		int p1 = *it;
		int p2 = N;
		if (it != (--gp.end())) {
			auto it2 = it;
			it2++;
			p2 = *it2;
		}
		currn = st.query(p1, p2);
//		cout<<"at "<<p1<<" "<<p2<<endl;
//		cout<<"currn, currd: "<<currn<<" "<<currd<<endl;
		if (currn * bestd > bestn * currd) {
			bestn = currn;
			bestd = currd;
		}
		currd *= X[*it];	// update denominator
	}
//	cout<<"bestn, bestd: "<<bestn<<" "<<bestd<<endl;
	ll ans = norm(prodall * norm(bestn * inv(bestd)));
	return ans;
}

int init(int n, int x[], int y[]) {
	N = n;
	X = vi(N); Y = vi(N);
	for (int i = 0; i < N; i++) {
		X[i] = x[i];
		Y[i] = y[i];
	}
	st.init(N);
	for (int i = 0; i < N; i++) {
		st.upd(i, Y[i]);
	}
/*	cout<<"st: ";
	for (int i = 0; i < st.sz * 2; i++) {
		cout<<st.vals[i]<<" ";
	}
	cout<<endl;*/
	for (int i = 0; i < N; i++) {
		if (X[i] != 1)
			gp.insert(i);
	}
	gp.insert(-1);
	for (int i = 0; i < N; i++) {
		prodall *= X[i];
		prodall = norm(prodall);
	}
	ll ans = solve();
	return (int)(ans);
}

int updateX(int pos, int val) {
	if (X[pos] != 1 && val == 1)
		gp.erase(pos);
	if (X[pos] == 1 && val != 1)
		gp.insert(pos);
	prodall = norm(prodall * inv(X[pos]));
	X[pos] = val;
	prodall = norm(prodall * X[pos]);
	ll ans = solve();
	return (int)(ans);
}

int updateY(int pos, int val) {
	Y[pos] = val;
	st.upd(pos, val);
	ll ans = solve();
	return (int)(ans);
}

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