Submission #1185771

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185771		sano	말 (IOI15_horses)	C++20	17 / 100	377 ms	72768 KiB

horses

//#pragma GCC optimize("O3")
//#pragma GCC target("tune=native")
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include "horses.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#include <cassert>
#include <bitset>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

#define shit short int
#define ll long long
//#define int ll
#define For(i, n) for(int i = 0; i < (int)n; i++)
#define ffor(i, a, n) for(int i = (int)a; i < (int)n; i++)
#define rfor(i, n) for(int i = (int)n; i >= (int)0; i--)
#define rffor(i, a, n) for(int i = (int)n; i >= (int)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<int, int>
#define NEK 2000000000
#define mod 1000000007
#define mod2 1000000009
#define rsz resize
#define prv1 47
#define prv2 43
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define all(x) (x).begin(), (x).end()
#define sig 0.0000001

using namespace std;
//using namespace __gnu_pbds;

//template <typename T1, typename T2>
//using indexed_set = tree<pair<T1, T2>, null_type, less<pair<T1, T2>>, rb_tree_tag, tree_order_statistics_node_update>;

ll umocni(ll a, ll b) {
	ll vys = 1;
	while (b) {
		if (b & 1) {
			vys *= a;
			vys %= mod;
		}
		a *= a;
		a %= mod;
		b /= 2;
	}
	return vys;
}

class intervalac_max {
	int n;
	vec<ll> l, r, in;
	void update(ll s) {
		in[s] = max(in[s * 2], in[s * 2 + 1]);
		return;
	}
public:
	void postav(ll vel) {
		n = 1;
		while (n < vel) n *= 2;
		r.resize(2 * n); l.resize(2 * n); in.resize(2 * n);
		For(i, n) r[i + n] = l[i + n] = i;
		rffor(i, 1, n - 1) {
			l[i] = l[i * 2];
			r[i] = r[i * 2 + 1];
		}
		return;
	}
	void zmen(ll a, ll b) {
		a += n;
		in[a] = b;
		a /= 2;
		while (a) {
			update(a);
			a /= 2;
		}
		return;
	}
	ll daj(ll a, ll b, ll s = 1) {
		if (l[s] > b || r[s] < a) return 0;
		if (a <= l[s] && r[s] <= b) return in[s];
		return max(daj(a, b, s * 2), daj(a, b, s * 2 + 1));
	}
};

class intervalac_suc {
	int n;
	vec<int> l, r, in;
	void update(ll s) {
		in[s] = in[s * 2] * in[s * 2 + 1];
		in[s] %= mod;
		return;
	}
public:
	void postav(ll vel) {
		n = 1;
		while (n < vel) n *= 2;
		r.resize(2 * n); l.resize(2 * n); in.resize(2 * n, 1);
		For(i, n) r[i + n] = l[i + n] = i;
		rffor(i, 1, n - 1) {
			l[i] = l[i * 2];
			r[i] = r[i * 2 + 1];
		}
		return;
	}
	void zmen(ll a, ll b) {
		a += n;
		in[a] = b;
		a /= 2;
		while (a) {
			update(a);
			a /= 2;
		}
		return;
	}
	ll daj(ll a, ll b, ll s = 1) {
		if (l[s] > b || r[s] < a) return 1;
		if (a <= l[s] && r[s] <= b) return in[s];
		return (daj(a, b, s * 2) * daj(a, b, s * 2 + 1)) % mod;
	}
};

vec<ll> x, y;
set<pii> sx;
intervalac_max segy;
intervalac_suc segx;

int zisti() {
	ll n = x.size();
	ll suc = 1;
	long double maxi = 0;
	ll max_y = -1;
	ll pr = n - 1;
	ll maxi_hod = 0;
	for (auto i : sx) {
		ll som = i.ff * (-1);
		max_y = max(max_y, segy.daj(som, pr));
		long double n_max_y = max_y;
		long double suc2 = suc;
		long double podiel = n_max_y / suc2;
		if (maxi < podiel) {
			maxi = podiel;
			maxi_hod = (segx.daj(0, som) * max_y) % mod;
		}
		maxi = max(maxi, n_max_y / suc2);
		pr = som;
		suc *= i.ss;
		if (suc >= mod) break;
	}
	if (suc < mod) {
		max_y = max(max_y, segy.daj(0, pr));
		long double suc2 = suc;
		long double n_max_y = max_y;
		long double podiel = n_max_y / suc2;
		if (maxi < podiel) {
			maxi = podiel;
			maxi_hod = max_y;
		}
	}
	return maxi_hod;
}

int init(int n, int x2[], int y2[]) {
	x.resize(n, 1);
	y.resize(n, 1);
	segx.postav(n), segy.postav(n);
	For(i, n) {
		x[i] = x2[i];
		if (x[i] != 1) sx.insert({ i * (-1), x[i] });
		segx.zmen(i, x[i]);
		y[i] = y2[i];
		segy.zmen(i, y[i]);
	}
	return zisti();
}

int updateX(int pos, int val) {
	if (x[pos] != 1) sx.erase({ pos * (-1), x[pos] });
	if (val != 1) sx.insert({ pos * (-1), val });
	x[pos] = val;
	segx.zmen(pos, val);
	return zisti();
}

int updateY(int pos, int val) {
	y[pos] = val;
	segy.zmen(pos, val);
	return zisti();
}

/*
signed main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	//cin >> t;
	int n; cin >> n;
	int x2[100], y2[100];
	For(i, n) cin >> x2[i];
	For(i, n) cin >> y2[i];
	cout << init(n, x2, y2) << '\n';
	int q; cin >> q;
	For(i, q) {
		int t; cin >> t;
		if (t == 1) {
			int pos, val; cin >> pos >> val;
			cout << updateX(pos, val) << '\n';
		}
		if (t == 2) {
			int pos, val; cin >> pos >> val;
			cout << updateY(pos, val) << '\n';
		}
	}
	return 0;
}*/

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