oj.uz

Submission #110620

# Submission time Handle Problem Language Result Execution time Memory
110620 2019-05-11T14:36:53 Z m3r8 Dancing Elephants (IOI11_elephants) C++14
100 / 100
 5911 ms 14840 KB 
#include "elephants.h"
#include <stdio.h>
#include <string.h>
#include <cmath>
#include <algorithm>



typedef struct ele{
  int bc;
  int end;
  int bf;
  int pos;
  int id;
} ele;
ele bucket[1000][1000];
int sz[1000];
int anzB;
int n;
int l;
int sele[200000];
int bele[200000];
int ih[200000];
void calcB(int idx){
  int s = sz[idx];  
  int tmp = s-1;
  for(int i = s-1;i>=0;i--){
    if(bucket[idx][i].bf == -1 && (i == s-1 || bucket[idx][i+1].bf == -1)){
      bucket[idx][i].end = bucket[idx][i].pos + l;
      bucket[idx][i].bc = 1;
    }else{
      int b = bucket[idx][i].bf;
      if(b == -1){
        b = bucket[idx][i+1].bf;  
        bucket[idx][i].bf = b;
      };
      bucket[idx][i].end = bucket[idx][b].end;
      bucket[idx][i].bc = bucket[idx][b].bc + 1;
    };
    while(tmp != -1 && bucket[idx][tmp].pos +l >= bucket[idx][i].pos){
      tmp--;
    };
    if(tmp != -1){
      bucket[idx][tmp].bf = i;  
    };
  };
};
void delE(int idx, int id){
  int s = sz[idx]-1;  
  int tmp = bucket[idx][s].pos;
  int itmp = bucket[idx][s].id;
  while(s != 0 && itmp != id){
    std::swap(tmp,bucket[idx][s-1].pos);
    std::swap(itmp,bucket[idx][s-1].id);
    s--;
  };
  sz[idx]--;
  for(int i = 0;i<sz[idx];i++){
    bucket[idx][i].bf = -1; 
  };
  calcB(idx);
};
void insertE(int idx, int id, int pos){
  bele[id] = idx;
  int s = sz[idx]-1;  
  int tmp = s > -1 ?bucket[idx][s].pos:0;
  int itmp = s > -1 ?bucket[idx][s].id:0;
  while(s != -1 && tmp > pos){
    std::swap(tmp,bucket[idx][s+1].pos);
    std::swap(itmp,bucket[idx][s+1].id);
    s--;
    tmp = s > -1 ?bucket[idx][s].pos:0;
    itmp = s > -1 ?bucket[idx][s].id:0;
  //  printf("%d %d %d\n",tmp,pos,s);
  };
  bucket[idx][s+1].pos = pos;
  bucket[idx][s+1].id = id;
  sz[idx]++;
  for(int i = 0;i<sz[idx];i++){
    bucket[idx][i].bf = -1; 
  };
  calcB(idx);
};
int findN(int idx, int &aktP){
  int idxR = sz[idx]-1;
  int idxL = 0;
  if(bucket[idx][idxR].pos <= aktP){
    //printf("%d %d %d\n",idx,idxR,bucket[idx][idxR].pos);
    return 0;
  }else{
    while(idxR > idxL){
      int idxM = (idxR + idxL)/2;
      if(bucket[idx][idxM].pos <= aktP){
        idxL = idxM+1;  
      }else{
        idxR = idxM;  
      };
    };
    aktP = bucket[idx][idxL].end;
    return bucket[idx][idxL].bc;
  };  
};
int querry(){
  int aktP = 0;
  int aktC = 0;
  int first = 0;
  for(int i = 0;i<anzB;i++){
    if(sz[i]){
      if(!first){
        aktC += bucket[i][0].bc;  
        aktP += bucket[i][0].end;  
        first = 1;
        //printf("%d %d\n",aktC,aktP);
      }else{
        //printf("%d %d geil\n",sz[i],anzB);
        aktC += findN(i,aktP);  
        //printf("%d %d\n",aktC,aktP);
      };
    };
  };  
  return aktC;
};
void makeB(){
  anzB = std::ceil(std::sqrt(n));   
  int cnt = 0;
  int cnt1 = 0;
  for(int i = 0;i<anzB;i++){
    sz[i] = 0;  
  };
  for(int i = 0;i<n;i++){
    bucket[cnt][cnt1].pos = sele[i];
    bucket[cnt][cnt1].bf = -1;
    bucket[cnt][cnt1++].id = ih[i];
    bele[ih[i]] = cnt;
    if(cnt1 == anzB){
      sz[cnt] = cnt1;
      calcB(cnt);
      cnt1 = 0;  
      cnt++;
    };
  };
  if(cnt1){
    sz[cnt] = cnt1;
    calcB(cnt);
  };
};
void makeN(){
  int cnt = 0;
  for(int i = 0;i<anzB;i++){
    for(int j = 0;j<sz[i];j++){
      ih[cnt] = bucket[i][j].id;  
      sele[cnt] = bucket[i][j].pos;  
      cnt++;
    };
  };  
  makeB();
};
void printB(){
  for(int i = 0;i<anzB;i++){
    if(sz[i] == 0){
      printf("Empty");  
    };
    for(int j = 0;j<sz[i];j++){
      printf("(%d, %d, %d, %d, %d) ",bucket[i][j].pos,bucket[i][j].id,bucket[i][j].bc,bucket[i][j].end,bucket[i][j].bf);
      puts("");
    };
    puts("");
  };  
  puts("");
  puts("");
};

void init(int N, int L, int X[])
{
  n = N;
  l = L;
  for(int i = 0;i<n;i++){
    sele[i] = X[i];   
    ih[i] = i;
  };
  makeB();
  //printB();
}
int up = 0;

int update(int i, int y)
{
  int idx = bele[i];
  delE(idx,i);
  //printf("Delete\n");
  //printB();
  int ins = 0;
  for(int j = 0;j<anzB&&!ins;j++){
    if(sz[j]){
      if(bucket[j][sz[j]-1].pos >= y){
        if(bucket[j][0].pos >= y && j != 0){
          insertE(j-1,i,y);
        }else{
          insertE(j,i,y);
        };
        ins = 1;
      };
    };  
  };
  if(!ins){
    insertE(anzB-1,i,y);
  };
  //printf("querry\n");
  //printB();
  int erg = querry(); 
  if(up == anzB){
    makeN();  
    //printf("new\n");
    //printB();
    up = 0;
  }else{
    up++;  
  };
  return erg;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 266 ms 2780 KB Output is correct
8 Correct 346 ms 3176 KB Output is correct
9 Correct 442 ms 5316 KB Output is correct
10 Correct 398 ms 4856 KB Output is correct
11 Correct 374 ms 4852 KB Output is correct
12 Correct 764 ms 4984 KB Output is correct
13 Correct 493 ms 4728 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 266 ms 2780 KB Output is correct
8 Correct 346 ms 3176 KB Output is correct
9 Correct 442 ms 5316 KB Output is correct
10 Correct 398 ms 4856 KB Output is correct
11 Correct 374 ms 4852 KB Output is correct
12 Correct 764 ms 4984 KB Output is correct
13 Correct 493 ms 4728 KB Output is correct
14 Correct 297 ms 4072 KB Output is correct
15 Correct 548 ms 4208 KB Output is correct
16 Correct 1224 ms 5788 KB Output is correct
17 Correct 1646 ms 7012 KB Output is correct
18 Correct 1453 ms 6904 KB Output is correct
19 Correct 804 ms 7032 KB Output is correct
20 Correct 1484 ms 7052 KB Output is correct
21 Correct 1390 ms 7132 KB Output is correct
22 Correct 909 ms 6352 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 266 ms 2780 KB Output is correct
8 Correct 346 ms 3176 KB Output is correct
9 Correct 442 ms 5316 KB Output is correct
10 Correct 398 ms 4856 KB Output is correct
11 Correct 374 ms 4852 KB Output is correct
12 Correct 764 ms 4984 KB Output is correct
13 Correct 493 ms 4728 KB Output is correct
14 Correct 297 ms 4072 KB Output is correct
15 Correct 548 ms 4208 KB Output is correct
16 Correct 1224 ms 5788 KB Output is correct
17 Correct 1646 ms 7012 KB Output is correct
18 Correct 1453 ms 6904 KB Output is correct
19 Correct 804 ms 7032 KB Output is correct
20 Correct 1484 ms 7052 KB Output is correct
21 Correct 1390 ms 7132 KB Output is correct
22 Correct 909 ms 6352 KB Output is correct
23 Correct 4398 ms 11896 KB Output is correct
24 Correct 3840 ms 11928 KB Output is correct
25 Correct 2975 ms 11932 KB Output is correct
26 Correct 3718 ms 11832 KB Output is correct
27 Correct 3654 ms 11768 KB Output is correct
28 Correct 696 ms 5368 KB Output is correct
29 Correct 592 ms 5240 KB Output is correct
30 Correct 712 ms 5240 KB Output is correct
31 Correct 614 ms 5412 KB Output is correct
32 Correct 3049 ms 11768 KB Output is correct
33 Correct 2118 ms 11764 KB Output is correct
34 Correct 3213 ms 11740 KB Output is correct
35 Correct 2349 ms 14840 KB Output is correct
36 Correct 2051 ms 11848 KB Output is correct
37 Correct 4996 ms 13432 KB Output is correct
38 Correct 2863 ms 11640 KB Output is correct
39 Correct 3167 ms 11768 KB Output is correct
40 Correct 3254 ms 11844 KB Output is correct
41 Correct 5531 ms 11952 KB Output is correct
42 Correct 5911 ms 11904 KB Output is correct