oj.uz

Submission #805510

# Submission time Handle Problem Language Result Execution time Memory
805510 2023-08-03T17:18:17 Z QwertyPi Dancing Elephants (IOI11_elephants) C++14
100 / 100
 8871 ms 18468 KB 
#include "elephants.h"
#include <bits/stdc++.h>

const int MAXN = 1.5e5 + 11;
const int SQ = 400;
int n, l;
int x[MAXN], _x[MAXN];

using namespace std;

struct naive{
    int n, y[SQ * 2 + 1], dp[SQ * 2 + 1], fin[SQ * 2 + 1];
    void build(int n, int x[]){
        naive::n = n;
        for(int i = 0; i < n; i++){
            y[i] = x[i];
        }
        precalc();
    }
    void rem(int x){
        int i; for(i = 0; i < n; i++) if(y[i] == x) break;
        for(int j = i; j < n - 1; j++) y[j] = y[j + 1];
        n--; precalc();
    }
    void add(int x){
        int i; for(i = 0; i < n; i++) if(y[i] > x) break;
        for(int j = n - 1; j >= i; j--) y[j + 1] = y[j];
        y[i] = x;
        n++; precalc();
    }
    void precalc(){
        dp[n] = 0; fin[n] = n; int r = n - 1;
        for(int j = n - 1; j >= 0; j--){
            while(y[r] - y[j] > l) r--;
            dp[j] = dp[r + 1] + 1;
            fin[j] = r + 1 != n ? fin[r + 1] : j;
        }
    }
    pair<int, int> qry(int x){
        int id = upper_bound(y, y + n, x) - y;
        if(id == n) return {0, 0};
        return {dp[id], y[fin[id]]};
    }
} cal[MAXN / SQ + 10];

int B[MAXN / SQ + 10], size_B;
unordered_map<int, int> mp;
void rebuild(){
    mp.clear(); for(int i = 0; i < n; i++) mp[_x[i]]++;
    for(int i = 0; i < n; i++) x[i] = _x[i];
    std::sort(x, x + n); int k = unique(x, x + n) - x;
    B[0] = 0;
    for(int i = 1; i < (k + SQ - 1) / SQ; i++){
        B[i] = x[SQ * i];
    }
    B[(k + SQ - 1) / SQ] = 1 << 30;
    size_B = (k + SQ - 1) / SQ;
    for(int i = 0; i < (k + SQ - 1) / SQ; i++){
        cal[i].build(min(SQ, k - i * SQ), x + i * SQ);
    }
}

void rem(int x){
    mp[x]--; if(mp[x] > 0) return;
    int id = upper_bound(B, B + size_B, x) - B - 1;
    cal[id].rem(x);
}

void add(int x){
    mp[x]++; if(mp[x] > 1) return;
    int id = upper_bound(B, B + size_B, x) - B - 1;
    cal[id].add(x);
}

int qry(){
    int ans = 0, x = -1, b = 0;
    for(int b = 0; b < size_B; b++){
        if(x >= B[b + 1]) continue;
        pair<int, int> p = cal[b].qry(x);
        ans += p.first; if(p.first != 0) x = p.second + l;
    }
    return ans;
}

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

int uid = 0;
int update(int i, int y){
    rem(_x[i]);
    _x[i] = y;
    add(_x[i]);
    uid++; if(uid % SQ == 0) rebuild();
    return qry();
}

Compilation message

elephants.cpp: In function 'int qry()':
elephants.cpp:76:26: warning: unused variable 'b' [-Wunused-variable]
   76 |     int ans = 0, x = -1, b = 0;
      |                          ^

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 225 ms 1944 KB Output is correct
8 Correct 274 ms 2280 KB Output is correct
9 Correct 444 ms 4952 KB Output is correct
10 Correct 647 ms 4876 KB Output is correct
11 Correct 647 ms 4964 KB Output is correct
12 Correct 1012 ms 4964 KB Output is correct
13 Correct 550 ms 4956 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 225 ms 1944 KB Output is correct
8 Correct 274 ms 2280 KB Output is correct
9 Correct 444 ms 4952 KB Output is correct
10 Correct 647 ms 4876 KB Output is correct
11 Correct 647 ms 4964 KB Output is correct
12 Correct 1012 ms 4964 KB Output is correct
13 Correct 550 ms 4956 KB Output is correct
14 Correct 265 ms 2516 KB Output is correct
15 Correct 485 ms 4488 KB Output is correct
16 Correct 1484 ms 6988 KB Output is correct
17 Correct 1957 ms 8536 KB Output is correct
18 Correct 2057 ms 8464 KB Output is correct
19 Correct 1067 ms 8668 KB Output is correct
20 Correct 1955 ms 8536 KB Output is correct
21 Correct 1906 ms 8496 KB Output is correct
22 Correct 1016 ms 8100 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 225 ms 1944 KB Output is correct
8 Correct 274 ms 2280 KB Output is correct
9 Correct 444 ms 4952 KB Output is correct
10 Correct 647 ms 4876 KB Output is correct
11 Correct 647 ms 4964 KB Output is correct
12 Correct 1012 ms 4964 KB Output is correct
13 Correct 550 ms 4956 KB Output is correct
14 Correct 265 ms 2516 KB Output is correct
15 Correct 485 ms 4488 KB Output is correct
16 Correct 1484 ms 6988 KB Output is correct
17 Correct 1957 ms 8536 KB Output is correct
18 Correct 2057 ms 8464 KB Output is correct
19 Correct 1067 ms 8668 KB Output is correct
20 Correct 1955 ms 8536 KB Output is correct
21 Correct 1906 ms 8496 KB Output is correct
22 Correct 1016 ms 8100 KB Output is correct
23 Correct 5922 ms 18464 KB Output is correct
24 Correct 6187 ms 18468 KB Output is correct
25 Correct 3742 ms 18456 KB Output is correct
26 Correct 6396 ms 18468 KB Output is correct
27 Correct 6890 ms 18312 KB Output is correct
28 Correct 916 ms 5452 KB Output is correct
29 Correct 839 ms 5356 KB Output is correct
30 Correct 926 ms 5436 KB Output is correct
31 Correct 838 ms 5388 KB Output is correct
32 Correct 5506 ms 17904 KB Output is correct
33 Correct 3174 ms 17208 KB Output is correct
34 Correct 5434 ms 18108 KB Output is correct
35 Correct 2782 ms 18344 KB Output is correct
36 Correct 1058 ms 8288 KB Output is correct
37 Correct 5399 ms 18204 KB Output is correct
38 Correct 4429 ms 17200 KB Output is correct
39 Correct 4573 ms 18144 KB Output is correct
40 Correct 4435 ms 17136 KB Output is correct
41 Correct 8871 ms 17884 KB Output is correct
42 Correct 8754 ms 18184 KB Output is correct