| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 157379 | diegogrc | Dancing Elephants (IOI11_elephants) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// Copyright © 2019 Diego Garcia Rodriguez del Campo. All rights reserved.
#include<bits/stdc++.h>
#define MAX 200005
#define optimiza_io cin.tie(0); ios_base::sync_with_stdio(0);
using namespace std;
typedef long long i64;
int N, L, M, K, cnt;
vector < int > buck[400];
vector < int > to[400];
vector < int > numpics[400];
vector < int > ini;
void calcBucket( int i ) {
// Calculate numpics and to back to front
int pt = buck[i].size() - 1;
for( int j = buck[i].size() - 1; j >= 0; j -- ) {
while( buck[i][pt] - buck[i][j] > L )
pt--;
if( pt == buck[i].size() - 1 ) {
numpics[i][j] = 1;
to[i][j] = buck[i][j] + L;
}
else {
int sig = pt + 1;
numpics[i][j] = numpics[i][sig] + 1;
to[i][j] = to[i][sig];
}
}
}
void createBuckets( vector < int > & a ) {
// Empty buckets
for( int i = 1; i <= K; i ++ ) {
buck[i].clear();
to[i].clear();
numpics[i].clear();
}
for( int i = 0; i < a.size(); i ++ ) {
int cub = ceil( ( double ) ( i + 1 ) / ( double ) K );
cub = min( cub , K );
buck[cub].push_back( a[i] );
to[cub].push_back( 0 );
numpics[cub].push_back( 0 );
}
// For every bucket
for( int i = 1; i <= K; i ++ )
calcBucket( i );
}
void redistributeBuckets() {
vector < int > a;
for( int i = 1; i <= K; i ++ )
for( auto v : buck[i] )
a.push_back( v );
createBuckets( a );
}
int findBucket( int x ) {
int lst = 0;
for( int i = 1; i <= K; i ++ )
if( buck[i].size() > 0 && buck[i][buck[i].size() - 1] < x )
lst = i;
return lst == K ? lst : lst + 1;
}
void deleteElephant( int x ) {
// Find Bucket
int b = findBucket( x );
int i = 0;
while( buck[b][i] != x )
i++;
for( int j = i; j < buck[b].size() - 1; j ++ )
buck[b][j] = buck[b][j + 1];
buck[b].pop_back();
to[b].pop_back();
numpics[b].pop_back();
// Recalculate Bucket
calcBucket( b );
}
void addElephant( int x ) {
// Find Bucket
int b = findBucket( x );
buck[b].push_back( x );
to[b].push_back( 0 );
numpics[b].push_back( 0 );
int i = buck[b].size() - 1;
while( i - 1 >= 0 && buck[b][i - 1] > buck[b][i] ) {
swap( buck[b][i - 1] , buck[b][i] );
i--;
}
// Recalculate Bucket
calcBucket( b );
}
int getNumPics() {
int b = 1;
while( buck[b].size() == 0 )
b++;
int ans = 0;
int idx = 0;
while( b <= K ) {
ans += numpics[b][idx];
int sig = to[b][idx];
// Look for next bucket
int nxtB = b;
while( nxtB <= K && ( buck[nxtB].size() == 0 or buck[nxtB][buck[nxtB].size() - 1] <= sig ) )
nxtB++;
if( nxtB > K )
break;
b = nxtB;
int l = 0, r = buck[b].size() - 1;
while( l < r ) {
int mid = ( l + r ) / 2;
if( buck[b][mid] > sig )
r = mid;
else
l = mid + 1;
}
idx = l;
}
return ans;
}
int main()
{
optimiza_io
scanf("%d%d%d" , & N , & L , & M );
K = sqrt( N ) + 1;
for( int i = 1; i <= N; i ++ ) {
int x;
scanf("%d" , & x );
ini.push_back( x );
}
vector < int > in2 = ini;
sort( in2.begin() , in2.end() );
createBuckets( in2 );
while( M -- ) {
int p, x;
scanf("%d%d" , & p , & x );
deleteElephant( ini[p] );
ini[p] = x;
addElephant( ini[p] );
printf("%d\n" , getNumPics() );
// Check if need to redistribute buckets
cnt++;
if( cnt >= ceil( ( double ) N / ( double ) K ) ) {
cnt = 0;
redistributeBuckets();
}
}
return 0;
}