oj.uz

Submission #14776

# Submission time Handle Problem Language Result Execution time Memory
14776 2015-06-22T09:11:39 Z minsu Dancing Elephants (IOI11_elephants) C++14
100 / 100
 6607 ms 22272 KB 
#include <bits/stdc++.h>
#include "elephants.h"
using namespace std;
#define MAXE 150051
#define BLOCK 400

int n, bn, l, ele[MAXE], tmp[MAXE], cooltime;
int p[BLOCK][BLOCK*2], sz[BLOCK][BLOCK*2], la[BLOCK][BLOCK*2], pn[BLOCK], pl[BLOCK];

void calc(int b){
  for(int i=pn[b]-1; i>=0; i--){
    int nxt = lower_bound( p[b]+i+1, p[b]+pn[b], p[b][i] + l + 1 ) - p[b];
    if( nxt == pn[b] ) sz[b][i] = 1, la[b][i] = p[b][i] + l + 1;
    else sz[b][i] = sz[b][nxt] + 1, la[b][i] = la[b][nxt];
  }
}

void mkblock( int X[] ){
  for(int i=0; i<bn; i++) pn[i] = 0;
  for(int i=0; i<n; i++){
    int b = i / BLOCK;
    int& bs = pn[b];
    p[b][bs++] = X[i];
  } bn = ( n-1 ) / BLOCK + 1;
  for(int i=0; i<bn; i++)
    calc(i), pl[i] = p[i][pn[i]-1];
}

void init(int N, int L, int X[]){
  n = N; l = L;
  for(int i=0;i<n;i++) ele[i] = X[i];
  mkblock( X );
}

int update(int i, int y)
{
  if( ++cooltime == BLOCK ){
    cooltime = 0;
    bool xd = false, ya = false; int tn = 0, x;
    x = ele[i]; ele[i] = y;
    for(int i=0; i<bn; i++)
      for(int j=0; j<pn[i]; j++){
        if( !xd && p[i][j] == x ) { xd = true; continue; }
        if( !ya && p[i][j] > y ) { ya = true; tmp[tn++] = y; }
        tmp[tn++] = p[i][j];
      }
    if(!ya) tmp[tn++] = y;
    mkblock( tmp );   
  }else{
    int xb = lower_bound( pl, pl + bn, ele[i] ) - pl;
    int xp = lower_bound( p[xb], p[xb] + pn[xb], ele[i] ) - p[xb];
    pn[xb]--; for(int i=xp; i<pn[xb]; i++) p[xb][i] = p[xb][i+1];
    calc(xb); if(pn[xb]!=0) pl[xb] = p[xb][pn[xb]-1];

    ele[i] = y;
    int yb = lower_bound( pl, pl + bn, ele[i] ) - pl; if(yb == bn) yb--;
    int yp = lower_bound( p[yb], p[yb] + pn[yb], ele[i] ) - p[yb];
    for(int i=pn[yb]; i>yp; i--) p[yb][i] = p[yb][i-1]; pn[yb]++; p[yb][yp] = ele[i];
    calc(yb); pl[yb] = p[yb][pn[yb]-1];
  }

  int ret = 0, pos = -1;
  for(int i=0; i<bn; i++){
    int j = lower_bound( p[i], p[i] + pn[i], pos ) - p[i];
    if( j == pn[i] ) continue;
    ret += sz[i][j]; pos = la[i][j];
  }
  return ret;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 861 ms 22272 KB Output is correct
2 Correct 888 ms 22272 KB Output is correct
3 Correct 945 ms 22272 KB Output is correct
4 Correct 1091 ms 22272 KB Output is correct
5 Correct 1061 ms 22272 KB Output is correct
6 Correct 1216 ms 22272 KB Output is correct
7 Correct 1223 ms 22272 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1232 ms 22272 KB Output is correct
2 Correct 1270 ms 22272 KB Output is correct
3 Correct 1943 ms 22272 KB Output is correct
4 Correct 1997 ms 22272 KB Output is correct
5 Correct 2135 ms 22272 KB Output is correct
6 Correct 1510 ms 22272 KB Output is correct
7 Correct 1982 ms 22272 KB Output is correct
8 Correct 1926 ms 22272 KB Output is correct
9 Correct 1862 ms 22272 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5373 ms 22272 KB Output is correct
2 Correct 5594 ms 22272 KB Output is correct
3 Correct 4460 ms 22272 KB Output is correct
4 Correct 5458 ms 22272 KB Output is correct
5 Correct 5325 ms 22272 KB Output is correct
6 Correct 4275 ms 22272 KB Output is correct
7 Correct 4524 ms 22272 KB Output is correct
8 Correct 4257 ms 22272 KB Output is correct
9 Correct 4520 ms 22272 KB Output is correct
10 Correct 5187 ms 22272 KB Output is correct
11 Correct 4753 ms 22272 KB Output is correct
12 Correct 5055 ms 22272 KB Output is correct
13 Correct 5533 ms 22272 KB Output is correct
14 Correct 6080 ms 22272 KB Output is correct
15 Correct 5046 ms 22272 KB Output is correct
16 Correct 5446 ms 22272 KB Output is correct
17 Correct 4599 ms 22272 KB Output is correct
18 Correct 6607 ms 22272 KB Output is correct
19 Correct 6084 ms 22272 KB Output is correct
20 Correct 6165 ms 22272 KB Output is correct