oj.uz

답안 #29110

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
29110 2017-07-18T09:34:46 Z osmanorhan 코끼리 (Dancing Elephants) (IOI11_elephants) C++14
97 / 100
 9000 ms 21852 KB 
#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];
	//~ printf("asdasdasd %d %d\n",gr[n],ar[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++ ) {
		//~ printf("asdasdasd %d %d(%d %d)\n",*it,n,ar[*it],ar[n]);
		if( ar[*it] >= ar[n] ) { w[t].insert( it , n ); c=1; break; }
		
	}
	//~ printf("--- %d\n",c);
	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];
	
	erase( id );
	
	ar[id] = nv;
	
	add( id );
	
	//~ printf("------------------------------------------------/ %d\n",ng);
	//~ for(int i=0;i<ng;i++) {
		//~ printf("---------- %d -----------\n",i);
		//~ for(int j=0;j<w[i].size();j++)
			//~ printf("%d %d (%d %d)\n",w[i][j],ar[w[i][j]],f[w[i][j]],g[w[i][j]]);
		//~ printf("------ finish\n");
	//~ }

	int ans = 0;
	
	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;
		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++;
		//~ printf("%d %d\n",i,t);
		if( t < w[i].size() ) {
			back = g[w[i][t]];
			ans += f[w[i][t]];
		}
	}
	//~ printf("asdasdasd ==> %d\n",ans);
	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();
	//~ printf("------------------------------------------------/ %d\n",ng);
	//~ for(int i=0;i<ng;i++) {
		//~ printf("---------- %d -----------\n",i);
		//~ for(int j=0;j<w[i].size();j++)
			//~ printf("%d ",w[i][j]);
		//~ printf("\n");
	//~ }
	
}

Compilation message

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:134: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:137:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if( t < w[i].size() ) {
         ^
elephants.cpp:111:6: warning: unused variable 't' [-Wunused-variable]
  int t = ar[id];
      ^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 21064 KB Output is correct
2 Correct 0 ms 21060 KB Output is correct
3 Correct 3 ms 21060 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 21056 KB Output is correct
2 Correct 0 ms 21060 KB Output is correct
3 Correct 0 ms 21056 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 703 ms 21192 KB Output is correct
2 Correct 936 ms 21188 KB Output is correct
3 Correct 1663 ms 21320 KB Output is correct
4 Correct 2106 ms 21328 KB Output is correct
5 Correct 1476 ms 21320 KB Output is correct
6 Correct 3149 ms 21320 KB Output is correct
7 Correct 2269 ms 21320 KB Output is correct

Subtask #4
47.0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1263 ms 21324 KB Output is correct
2 Correct 1459 ms 21192 KB Output is correct
3 Correct 4006 ms 21328 KB Output is correct
4 Correct 6073 ms 21592 KB Output is correct
5 Correct 5926 ms 21584 KB Output is correct
6 Correct 4556 ms 21588 KB Output is correct
7 Correct 5909 ms 21588 KB Output is correct
8 Correct 6053 ms 21588 KB Output is correct
9 Correct 4346 ms 21588 KB Output is correct

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 9000 ms 21852 KB Execution timed out
2 Halted 0 ms 0 KB -