Submission #1162011

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162011		sano	Dancing Elephants (IOI11_elephants)	C++20	97 / 100	9084 ms	11628 KiB

elephants

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

using namespace std;

ll n, l;

vec<vec<ll>> mp;
vec<ll> kde;
vec<ll> a;
vec<ll> st;
vec<vec<pii>> dp;

void init(int n2, int l2, int x2[]) {
	n = n2, l = l2;
	vec<ll> x;
	For(i, n) x.push_back(x2[i]);
	a = x;
	return;
}

void prepocitaj(ll x) {
	if (mp[x].size() == 0) return;
	dp[x].clear();
	dp[x].resize(mp[x].size());
	ll pos = mp[x].back();
	rfor(i, mp[x].size() - 1) {
		ll poz = mp[x][i] + l;
		if (poz >= pos) {
			dp[x][i] = { 1, poz };
			continue;
		}
		ll dosah = upper_bound(mp[x].begin(), mp[x].end(), poz) - mp[x].begin();
		dp[x][i] = { dp[x][dosah].ff + 1, dp[x][dosah].ss };
	}
	return;
}


void postav() {
	mp.clear();
	st.clear();
	kde.clear();
	dp.clear();
	ll sq = sqrt(n);
	if (sq * sq < n) sq++;
	mp.resize(sq);
	st.resize(sq, NEK);
	kde.resize(n, -1);
	dp.resize(sq);
	vec<pii> na;
	For(i, a.size()) {
		na.push_back({ a[i], i });
	}
	sort(na.begin(), na.end());
	For(i, n) {
		mp[i / sq].push_back(na[i].ff);
		kde[na[i].ss] = i / sq;
		st[i / sq] = min(st[i / sq], na[i].ff);
	}
	For(i, sq) {
		prepocitaj(i);
	}
	return;
}


ll zostav() {
	ll vys = 0;
	ll som = -1;
	For(i, dp.size()) {
		if (dp[i].size() == 0) continue;
		ll poz = upper_bound(mp[i].begin(), mp[i].end(), som) - mp[i].begin();
		if (poz == mp[i].size()) continue;
		vys += dp[i][poz].ff;
		som = dp[i][poz].ss;
	}
	return vys;
}

ll spravny_cas = 275;

ll cas = spravny_cas;

ll update(int x222, int k222) {
	ll x = x222, k = k222;
	if (cas == spravny_cas) {
		cas = 0;
		postav();
	}
	cas++;
	ll x2 = kde[x];
	vec<ll> no;
	bool mame = 0;
	For(i, mp[x2].size()) {
		if (mp[x2][i] == a[x] && mame == 0) { mame = 1; continue; }
		no.push_back(mp[x2][i]);
	}
	mp[x2] = no;
	ll x3 = lower_bound(st.begin(), st.end(), k) - st.begin();
	if (x3 != 0) x3--;
	st[x3] = min(st[x3], k);
	no.clear();
	mame = 0;
	For(i, mp[x3].size()) {
		if (mp[x3][i] > k && mame == 0) { no.push_back(k); mame = 1; }
		no.push_back(mp[x3][i]);
	}
	if (!mame) {
		no.push_back(k);
	}
	mp[x3] = no;
	a[x] = k;
	kde[x] = x3;
	prepocitaj(x2); prepocitaj(x3);
	return zostav();
}
/*
signed main() {
	//ll t; cin >> t;
	ll t = 1;
	For(w, t) {
		int n, l, m; cin >> n >> l >> m;
		spravny_cas = sqrt(m);
		cas = spravny_cas;
		int aa[100]; For(i, n) cin >> aa[i];
		init(n, l, aa);
		For(i, m) {
			ll a, b; cin >> a >> b;
			cout << update(a, b) << '\n';
		}
	}
	return 0;
}*/

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 0 / 3