| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1162010 | sano | 코끼리 (Dancing Elephants) (IOI11_elephants) | C++20 | 0 ms | 0 KiB |
//#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;
}