Submission #1191027

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191027		pcheloveks	Peru (RMI20_peru)	C++20	49 / 100	1062 ms	285132 KiB

peru

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
//#pragma GCC target("bmi,bmi2,popcnt,lzcnt")

//Andrusha Holod did not qualify to IOI 2025 )))
//Hope Andrusha Holod will win IOI 2026

#include "peru.h"

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <fstream>
#include <climits>
#include <queue>
#include <algorithm>
#include <stdint.h>
#include <stack>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <cstring> // Для memset

#define endl '\n'

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

typedef pair < ll, ull > piu;
typedef pair <ll, ll> pii;
typedef pair <ld, ld> pdd;

const ll DIM = 100007;
const ll MXMASK = (1 << 21);
const ll INF = 1e18;
const ll mod = 1e9 + 7;
const ld eps = 0.00000000001;
const ld gr = (sqrt(5) + 1) / 2;
const ll offset = 10000;
const ll Bits = 20;

const ll dx[5] = { -1, -1, 0, 1, 0 };
const ll dy[5] = { -1, 0, -1, 0, 1 };

FILE* stream;

class segmentTree {
public:

	void init(ll sz_) {
		sz = sz_;
		T.resize(4 * sz + 4);

		build(0, 0, sz - 1);
	}

	ll queryMi(ll L, ll R) {
		return queryMi(0, 0, sz - 1, L, R);
	}

	void updateF(ll pos, ll val) {
		updateF(0, 0, sz - 1, pos, val);
	}

	void updateMx(ll L, ll R, ll val) {
		if (L > R) return;
		updateMx(0, 0, sz - 1, L, R, val);
	}

private:

	struct node {
		ll mi, miF, mod;
	};

	ll sz;
	vector < node > T;

	void build(ll v, ll tl, ll tr) {
		if (tl == tr) {
			T[v] = { INF, INF, 0 };
			return;
		}

		ll tm = (tl + tr) / 2;
		build(2 * v + 1, tl, tm);
		build(2 * v + 2, tm + 1, tr);

		T[v].miF = min(T[2 * v + 1].miF, T[2 * v + 2].miF);
		T[v].mi = min(T[2 * v + 1].mi, T[2 * v + 2].mi);
		T[v].mod = 0;
	}

	void push(ll v) {
		if (T[v].mod == 0) return;
		T[2 * v + 1].mod = T[v].mod;
		T[2 * v + 1].mi = T[2 * v + 1].miF + T[v].mod;


		T[2 * v + 2].mod = T[v].mod;
		T[2 * v + 2].mi = T[2 * v + 2].miF + T[v].mod;

		T[v].mod = 0;
	}

	ll queryMi(ll v, ll tl, ll tr, ll L, ll R) {
		if (tl > R || tr < L) return INF;
		if (L <= tl && tr <= R) {
			return T[v].mi;
		}

		push(v);

		ll tm = (tl + tr) / 2;
		return min(queryMi(2 * v + 1, tl, tm, L, R), queryMi(2 * v + 2, tm + 1, tr, L, R));
	}

	void updateF(ll v, ll tl, ll tr, ll pos, ll val) {
		if (tl > pos || tr < pos) return;
		if (tl == tr) {
			T[v].miF = val;
			T[v].mi = T[v].mod + val;
			return;
		}

		push(v);

		ll tm = (tl + tr) / 2;
		updateF(2 * v + 1, tl, tm, pos, val);
		updateF(2 * v + 2, tm + 1, tr, pos, val);

		T[v].miF = min(T[2 * v + 1].miF, T[2 * v + 2].miF);
		T[v].mi = min(T[2 * v + 1].mi, T[2 * v + 2].mi);
	}

	void updateMx(ll v, ll tl, ll tr, ll L, ll R, ll val) {
		if (tl > R || tr < L) return;
		if (L <= tl && tr <= R) {
			T[v].mi = T[v].miF + val;
			T[v].mod = val;
			return;
		}

		push(v);

		ll tm = (tl + tr) / 2;
		updateMx(2 * v + 1, tl, tm, L, R, val);
		updateMx(2 * v + 2, tm + 1, tr, L, R, val);

		T[v].mi = min(T[2 * v + 1].mi, T[2 * v + 2].mi);
	}
};

int n, k;

int solve(int N, int K, int* S) {
	n = N;
	k = K;

	vector < ll > F(n);

	ll mx = -INF;

	segmentTree t;
	t.init(n + 7);

	for (int i = 0; i < k; i++) {
		mx = max((ll)S[i], mx);
		F[i] = mx;

		t.updateF(i, F[i]);
	}

	mx = 0;
	for (int i = k - 1; i >= 0; i--) {
		t.updateMx(i, i, mx);
		mx = max(mx, (ll)S[i]);
	}

	vector < ll > GreatL(n);
	stack < pii > s;

	for (int i = 0; i < n; i++) {
		while (!s.empty() && s.top().first <= S[i]) s.pop();
		if (s.empty()) GreatL[i] = -1;
		else GreatL[i] = s.top().second;
		s.push({ S[i], i });
	}

	for (int i = k; i < n; i++) {

		t.updateMx(GreatL[i], i - 1, S[i]);
		
		F[i] = t.queryMi(i - k, i - 1);
		t.updateF(i, F[i]);
	}

	vector < ll > powers(n);
	powers[0] = 1;
	for (int i = 1; i < n; i++) powers[i] = (powers[i - 1] * 23) % mod;

	ll res = 0;
	for (int i = 0; i < n; i++) {
		res += ( F[i] % mod ) * powers[n - 1 - i];
		res %= mod;
	}
	return res;
}

/*
5 4
8 9 10 11 3
*/

• Subtask 1: 18 / 18
• Subtask 2: 31 / 31
• Subtask 3: 0 / 51