Submission #157379

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
157379	2019-10-11T04:53:34 Z	diegogrc	Dancing Elephants (IOI11_elephants)	C++17	Compilation error	0 ms	0 KB

elephants

//  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;
}

Compilation message

elephants.cpp: In function 'void calcBucket(int)':
elephants.cpp:21:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if( pt == buck[i].size() - 1 ) {
             ~~~^~~~~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'void createBuckets(std::vector<int>&)':
elephants.cpp:43:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for( int i = 0; i < a.size(); i ++ ) {
                     ~~^~~~~~~~~~
elephants.cpp: In function 'void deleteElephant(int)':
elephants.cpp:80:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for( int j = i; j < buck[b].size() - 1; j ++ )
                     ~~^~~~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'int main()':
elephants.cpp:145:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d" , & N , & L , & M );
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
elephants.cpp:150:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d" , & x );
         ~~~~~^~~~~~~~~~~~~
elephants.cpp:161:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d" , & p , & x );
         ~~~~~^~~~~~~~~~~~~~~~~~~~~
/tmp/ccI7PHQL.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccTvHSFd.o:elephants.cpp:(.text.startup+0x0): first defined here
/tmp/ccI7PHQL.o: In function `main':
grader.cpp:(.text.startup+0x1d): undefined reference to `init(int, int, int*)'
grader.cpp:(.text.startup+0x3f): undefined reference to `update(int, int)'
collect2: error: ld returned 1 exit status