oj.uz

Submission #29175

# Submission time Handle Problem Language Result Execution time Memory
29175 2017-07-18T14:10:55 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];
	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();
}

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: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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 21060 KB Output is correct
2 Correct 0 ms 21060 KB Output is correct
3 Correct 0 ms 21060 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 21064 KB Output is correct
2 Correct 0 ms 21060 KB Output is correct
3 Correct 0 ms 21060 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 686 ms 21192 KB Output is correct
2 Correct 993 ms 21196 KB Output is correct
3 Correct 1939 ms 21320 KB Output is correct
4 Correct 2193 ms 21320 KB Output is correct
5 Correct 1549 ms 21328 KB Output is correct
6 Correct 2973 ms 21320 KB Output is correct
7 Correct 2016 ms 21328 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1279 ms 21324 KB Output is correct
2 Correct 1726 ms 21188 KB Output is correct
3 Correct 4433 ms 21324 KB Output is correct
4 Correct 6166 ms 21588 KB Output is correct
5 Correct 6133 ms 21588 KB Output is correct
6 Correct 4309 ms 21592 KB Output is correct
7 Correct 5853 ms 21592 KB Output is correct
8 Correct 6123 ms 21588 KB Output is correct
9 Correct 4529 ms 21588 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 9000 ms 21852 KB Execution timed out
2 Halted 0 ms 0 KB -