제출 #29175

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
29175		osmanorhan	코끼리 (Dancing Elephants) (IOI11_elephants)	C++14	97 / 100	9000 ms	21852 KiB

elephants

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <list>
#include <climits>
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <cassert>
#include <vector>
#define all(x) x.begin() , x.end()
#define fi first
#define se second
#define pb push_back
#define umax( x , y ) x = max( x , (y) )
#define umin( x , y ) x = min( x , (y) )
#define For( i , a ) for(int i=1;i<=a;i++)
#define ort (b+s)/2
#define y2 asrwjaelkf
#define y1 asseopirwjaelkf
 
using namespace std;
 
const int maxn = 150020;
const int kokn = 390;
const int MOd = 1e9+7;
 
typedef long long Lint;
typedef long double db;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
 
int K = 390;
int ng;
 
vector <int> w[kokn];
int a, L, ar[maxn], cnt;
int gr[maxn], f[maxn], g[maxn];
 
// build = kokn;
void build( int n ) {
	for(int i=w[n].size()-1,j=w[n].size()-1;i>=0;i--) {
		while( j >= 0 && ar[w[n][j]] > ar[w[n][i]]+L ) j--;
		if( j+1 < w[n].size() ) {
			g[w[n][i]] = g[w[n][j+1]];
			f[w[n][i]] = f[w[n][j+1]] + 1;
		} else {
			g[w[n][i]] = ar[w[n][i]]+L;
			f[w[n][i]] = 1;
		}
	}
}
 
// create = n * logn;
void create() {
	ii bs[maxn];
 
	for(int i=0;i<a;i++) bs[i].fi = ar[i], bs[i].se = i;
	sort( bs , bs+a );
 
	for(int i=0;i<=(a-1)/K+1;i++) w[i].clear();
 
	for(int i=0;i<a;i++) {
		w[i/K].pb( bs[i].se );
		gr[bs[i].se] = i/K;
	}
 
	for(int i=0;i<ng;i++)
		build( i );
}
 
// erase = kokn;
void erase( int n ) {
	int t = gr[n];
	int y = 0;
	for( vector <int> :: iterator it = w[t].begin() ; it != w[t].end() ; it++, y++ )
		if( *it == n ) { w[t].erase( it ); break; }
	build( t );
}
 
// add = kokn;
void add( int n ) {
	int t = 0;
	for(;t<ng-1;t++)
		if( w[t].size() && ar[n] < ar[w[t+1][0]] ) break;
	int c=0;
	for( vector <int> :: iterator it = w[t].begin() ; it != w[t].end() ; it++ )
		if( ar[*it] >= ar[n] ) { w[t].insert( it , n ); c=1; break; }
 
	if( !c ) w[t].insert( w[t].end() , n );
	gr[n] = t;
	build( t );
}
 
// update = kokn * logn;
int update( int id , int nv ) {
 
	++cnt;
 
	if( cnt % K == 0 ) create();
 
	int t = ar[id];
 
    //silme
	erase( id );
 
	ar[id] = nv;
 
    //ekleme
	add( id );
 
	int ans = 0;
 
    //cevabi hesaplama
	for(int i=0, back=-2;i<ng;i++) {
		if( !w[i].size() ) continue;
		if( i+1 < ng && w[i+1].size() && ar[w[i+1][0]] <= back ) continue;
      
      // binary search
		int t = -1;
		for(int k=9;k>=0;k--)
			if( t+(1<<k) < w[i].size() && ar[w[i][t+(1<<k)]] <= back ) t += (1<<k);
		t++;
      
		if( t < w[i].size() ) {
			back = g[w[i][t]];
			ans += f[w[i][t]];
		}
	}
 
	return ans;
}
 
void init( int n , int l , int xs[] ) {
	L = l;
	a = n;
	for(int i=0;i<a;i++) ar[i] = xs[i];
	K = sqrt( a ) + 1;
	ng = (a-1)/K+1;
	create();
}

컴파일 시 표준 에러 (stderr) 메시지

elephants.cpp: In function 'void build(int)':
elephants.cpp:49:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if( j+1 < w[n].size() ) {
           ^
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:127:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if( t+(1<<k) < w[i].size() && ar[w[i][t+(1<<k)]] <= back ) t += (1<<k);
                 ^
elephants.cpp:130:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if( t < w[i].size() ) {
         ^
elephants.cpp:107:6: warning: unused variable 't' [-Wunused-variable]
  int t = ar[id];
      ^

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