oj.uz

Submission #805501

# Submission time Handle Problem Language Result Execution time Memory
805501 2023-08-03T17:14:15 Z QwertyPi Dancing Elephants (IOI11_elephants) C++14
50 / 100
 724 ms 4204 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;
void rebuild(){
    for(int i = 0; i < n; i++) x[i] = _x[i];
    std::sort(x, x + n);
    B[0] = 0;
    for(int i = 1; i < (n + SQ - 1) / SQ; i++){
        B[i] = x[SQ * i];
    }
    B[(n + SQ - 1) / SQ] = 1 << 30;
    size_B = (n + SQ - 1) / SQ;
    for(int i = 0; i < (n + SQ - 1) / SQ; i++){
        cal[i].build(min(SQ, n - i * SQ), x + i * SQ);
    }
}

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

void add(int x){
    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:72:26: warning: unused variable 'b' [-Wunused-variable]
   72 |     int ans = 0, x = -1, b = 0;
      |                          ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 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 1 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 1 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 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 158 ms 1364 KB Output is correct
8 Correct 179 ms 2548 KB Output is correct
9 Correct 270 ms 4204 KB Output is correct
10 Correct 405 ms 4020 KB Output is correct
11 Correct 428 ms 3964 KB Output is correct
12 Correct 724 ms 4112 KB Output is correct
13 Correct 431 ms 3816 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 158 ms 1364 KB Output is correct
8 Correct 179 ms 2548 KB Output is correct
9 Correct 270 ms 4204 KB Output is correct
10 Correct 405 ms 4020 KB Output is correct
11 Correct 428 ms 3964 KB Output is correct
12 Correct 724 ms 4112 KB Output is correct
13 Correct 431 ms 3816 KB Output is correct
14 Incorrect 65 ms 3276 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 158 ms 1364 KB Output is correct
8 Correct 179 ms 2548 KB Output is correct
9 Correct 270 ms 4204 KB Output is correct
10 Correct 405 ms 4020 KB Output is correct
11 Correct 428 ms 3964 KB Output is correct
12 Correct 724 ms 4112 KB Output is correct
13 Correct 431 ms 3816 KB Output is correct
14 Incorrect 65 ms 3276 KB Output isn't correct
15 Halted 0 ms 0 KB -