이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define F first
#define S second
#define debug(x) cerr<<#x<<" :"<<x<<"\n"
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define FAST ios_base::sync_with_stdio(false), cin.tie(), cout.tie();
//#define int long long
typedef long long ll;
typedef long double ld;
const int maxn = 1.5e5 + 7;
const int mod = 1e9 + 7;
const int INF = 2e9 + 7;
const int mlog = 20;
const int SQRT = 400;
int n, k;
int bcnt;
int R[SQRT + 7];
int pos[maxn];
map<int, int> mp;
vector<int> jump[SQRT + 7], cnt[SQRT + 7], bucket[SQRT + 7];
void solve(int ind)
{
jump[ind] = vector<int>(bucket[ind].size());
cnt[ind] = vector<int>(bucket[ind].size());
for(int i = bucket[ind].size() - 1, j = bucket[ind].size(); ~i; i--)
{
while(bucket[ind][j - 1] > bucket[ind][i] + k)
j--;
if(j < (int)bucket[ind].size()) jump[ind][i] = jump[ind][j], cnt[ind][i] = cnt[ind][j] + 1;
else jump[ind][i] = bucket[ind][i] + k, cnt[ind][i] = 1;
}
}
void add(int x, bool rmv)
{
int ptr = -1;
while(R[++ptr] < x);
int ind = lower_bound(bucket[ptr].begin(), bucket[ptr].end(), x) - bucket[ptr].begin();
if(rmv) bucket[ptr].erase(bucket[ptr].begin() + ind);
else bucket[ptr].insert(bucket[ptr].begin() + ind, x);
solve(ptr);
}
void REBUILD()
{
bcnt = 0;
for(pii p : mp)
{
if(!bcnt || bucket[bcnt - 1].size() >= SQRT)
bucket[bcnt++].clear();
bucket[bcnt - 1].pb(p.F);
}
for(int i = 0; i < bcnt; i++)
{
if(i < bcnt - 1) R[i] = bucket[i + 1][0] - 1;
else R[i] = +INF;
solve(i);
}
}
void init(int _n, int _k, int X[])
{
n = _n, k = _k;
for(int i = 0; i < n; i++) ++mp[pos[i] = X[i]];
}
int cntBLOCK;
int update(int i,int y)
{
if(cntBLOCK++ % SQRT == 0)
REBUILD();
if(!--mp[pos[i]]) add(pos[i], 0), mp.erase(pos[i]);
if(!mp[y]) add(y, 1);
mp[y]++, pos[i] = y;
int ans = 0, cur = -1;
for(int i = 0; i < bcnt; i++)
{
int ind = upper_bound(bucket[i].begin(), bucket[i].end(), cur) - bucket[i].begin();
if(ind < (int)bucket[i].size())
ans += cnt[i][ind], cur = jump[i][ind];
}
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |