oj.uz

Submission #263184

# Submission time Handle Problem Language Result Execution time Memory
263184 2020-08-13T13:53:58 Z dantoh000 Dancing Elephants (IOI11_elephants) C++14
100 / 100
 4951 ms 16340 KB 
#include <bits/stdc++.h>
#define K 500
using namespace std;
//#include "elephants.h"
int n, l, x[150005];
int tmp[150005];
struct BUCKET{
    int a[150005], ct[150005], r[150005], sz;
    void comp(){
        int k = sz-1;
        for (int i = sz-1; i >= 0; i--){
            while (k > i && a[k-1] - a[i] > l) k--;
            if (a[sz-1] - a[i] <= l){
                ct[i] = 1; r[i] = a[i]+l;
            }
            else ct[i] = ct[k]+1, r[i] = r[k];
            //printf("%d -> %d: ct = %d, r = %d\n",a[i],a[k],ct[i],r[i]);
        }
    }
} bk[305];
void init(int N, int L, int X[])
{
  n = N;
  l = L;
  for (int i = 0; i < n; i++) x[i] = X[i];
  for (int i = 0; i <= n/K; i++){
        bk[i].sz = 0;
        for (int j = i*K; j < min((i+1)*K,n); j++){
            bk[i].a[j%K] = x[j];
            bk[i].sz++;
        }
        bk[i].comp();
  }
}
void rebuild_all(){
    //printf("REBUILD ALL");
    int N = 0;
    for (int i = 0; i <= n/K; i++){
        for (int j = 0; j < bk[i].sz; j++){
            tmp[N++] = bk[i].a[j];
        }
    }
    for (int i = 0; i <= n/K; i++){
        bk[i].sz = 0;
        for (int j = i*K; j < min((i+1)*K,n); j++){
            bk[i].a[j%K] = tmp[j];
            bk[i].sz++;
        }
        bk[i].comp();
    }
}

void add(int x){
    //printf("adding %d\n",x);
    for (int i = 0; i <= n/K; i++){
        if (i == (n-1)/K || (bk[i].sz && ((bk[i].a[0] > x) || (bk[i].a[0] <= x && x < bk[i+1].a[0])) )){
            //printf("adding to bucket %d\n",i);
            if (bk[i].sz == 0 || bk[i].a[0] > x){
                //printf("position %d\n",0);
                for (int k = bk[i].sz-1; k >= 0; k--){
                    bk[i].a[k+1] = bk[i].a[k];
                }
                bk[i].a[0] = x;

            }
            else{
                for (int j = 0; j < bk[i].sz; j++){
                    if ((bk[i].a[j] <= x && x < bk[i].a[j+1]) || j+1 == bk[i].sz){
                        //printf("position %d\n",j+1);
                        for (int k = bk[i].sz-1; k >= j+1; k--){
                            bk[i].a[k+1] = bk[i].a[k];
                        }
                        bk[i].a[j+1] = x;
                        break;
                    }
                }
            }
            bk[i].sz++;
            bk[i].comp();
            break;
        }
    }
}
void del(int x){
    // printf("deleting %d\n",x);
    for (int i = 0; i <= n/K; i++){
        if (bk[i].sz == 0) continue;
        if (bk[i].a[0] <= x && x <= bk[i].a[bk[i].sz-1]){
            //printf("deleting from bucket %d\n",i);
            for (int j = 0; j < bk[i].sz; j++){
                if (bk[i].a[j] == x){
                    //printf("position %d\n",j);
                    for (int k = j; k < bk[i].sz; k++){
                        bk[i].a[k] = bk[i].a[k+1];
                    }
                    break;
                }
            }
            bk[i].a[bk[i].sz] = 0;
            bk[i].sz--;
            bk[i].comp();
            break;
        }
    }
}
int hmmmmm;
int solve(){
    //printf("solving\n");
    int curpos = -1;
    int ans = 0;
    for (int i = 0; i <= n/K; i++){
        if (bk[i].sz == 0 || curpos >= bk[i].a[bk[i].sz-1]) continue;
        //printf("%d ",curpos);
        int nx = upper_bound(bk[i].a, bk[i].a+bk[i].sz,curpos) - bk[i].a;
        //printf("-> nx = %d (%d), ",nx,bk[i].a[nx]);
        //printf("add %d to %d\n",bk[i].ct[nx],ans);
        ans += bk[i].ct[nx];
        curpos = bk[i].r[nx];
    }
    return ans;

}
void debug(){
    int last = -1;
    int cur = 0;
    for (int i = 0; i <= n/K; i++){
        //printf("bucket %d: ",i);
        for (int j = 0; j <  bk[i].sz; j++){
            //printf("%d ",bk[i].a[j]);
            assert(bk[i].a[j] >= last);
            last= bk[i].a[j];

        }
        // printf("\n");
    }
}
int numQ = 0;
int update(int i, int y)
{

    hmmmmm++;
    //printf("up %d\n",hmmmmm);
    //printf("update %d %d->%d\n",i,x[i],y);
    if (++numQ == K){
        rebuild_all();
        numQ = 0;
    }
    del(x[i]);
    x[i] = y;
    add(x[i]);
    //debug();
    return solve();
}

Compilation message

elephants.cpp: In function 'void debug()':
elephants.cpp:126:9: warning: unused variable 'cur' [-Wunused-variable]
  126 |     int cur = 0;
      |         ^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 606 ms 1632 KB Output is correct
8 Correct 596 ms 1912 KB Output is correct
9 Correct 464 ms 3704 KB Output is correct
10 Correct 432 ms 3704 KB Output is correct
11 Correct 393 ms 3712 KB Output is correct
12 Correct 692 ms 3704 KB Output is correct
13 Correct 429 ms 3704 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 606 ms 1632 KB Output is correct
8 Correct 596 ms 1912 KB Output is correct
9 Correct 464 ms 3704 KB Output is correct
10 Correct 432 ms 3704 KB Output is correct
11 Correct 393 ms 3712 KB Output is correct
12 Correct 692 ms 3704 KB Output is correct
13 Correct 429 ms 3704 KB Output is correct
14 Correct 439 ms 2424 KB Output is correct
15 Correct 842 ms 3832 KB Output is correct
16 Correct 1216 ms 5752 KB Output is correct
17 Correct 1251 ms 7032 KB Output is correct
18 Correct 1381 ms 7160 KB Output is correct
19 Correct 727 ms 7160 KB Output is correct
20 Correct 1176 ms 7032 KB Output is correct
21 Correct 1142 ms 7160 KB Output is correct
22 Correct 734 ms 6780 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 606 ms 1632 KB Output is correct
8 Correct 596 ms 1912 KB Output is correct
9 Correct 464 ms 3704 KB Output is correct
10 Correct 432 ms 3704 KB Output is correct
11 Correct 393 ms 3712 KB Output is correct
12 Correct 692 ms 3704 KB Output is correct
13 Correct 429 ms 3704 KB Output is correct
14 Correct 439 ms 2424 KB Output is correct
15 Correct 842 ms 3832 KB Output is correct
16 Correct 1216 ms 5752 KB Output is correct
17 Correct 1251 ms 7032 KB Output is correct
18 Correct 1381 ms 7160 KB Output is correct
19 Correct 727 ms 7160 KB Output is correct
20 Correct 1176 ms 7032 KB Output is correct
21 Correct 1142 ms 7160 KB Output is correct
22 Correct 734 ms 6780 KB Output is correct
23 Correct 3984 ms 15380 KB Output is correct
24 Correct 4503 ms 15480 KB Output is correct
25 Correct 3707 ms 15356 KB Output is correct
26 Correct 4398 ms 15364 KB Output is correct
27 Correct 4760 ms 15216 KB Output is correct
28 Correct 2021 ms 5368 KB Output is correct
29 Correct 1926 ms 5436 KB Output is correct
30 Correct 1988 ms 5368 KB Output is correct
31 Correct 1913 ms 5352 KB Output is correct
32 Correct 2789 ms 14796 KB Output is correct
33 Correct 2025 ms 14140 KB Output is correct
34 Correct 3455 ms 15096 KB Output is correct
35 Correct 2071 ms 15296 KB Output is correct
36 Correct 1185 ms 14840 KB Output is correct
37 Correct 4067 ms 16340 KB Output is correct
38 Correct 3352 ms 14008 KB Output is correct
39 Correct 3847 ms 15040 KB Output is correct
40 Correct 3465 ms 14052 KB Output is correct
41 Correct 4784 ms 14788 KB Output is correct
42 Correct 4951 ms 15152 KB Output is correct