#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];
^
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
9000 ms |
21852 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
