oj.uz

Submission #975327

# Submission time Handle Problem Language Result Execution time Memory
975327 2024-05-04T19:11:38 Z fzyzzz_z Dancing Elephants (IOI11_elephants) C++17
26 / 100
 17 ms 9308 KB 
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long; 
 
const int mxn = 150005; 
const int B = 388, S = 387;
 
int n, k, a[mxn];
int f[B + 10], g[B + 10]; 
set<pair<int, int>> st[B + 10]; 
 
void updb(int b) {
    set<pair<int, int>>::reverse_iterator ri; 
    for (ri = st[b].rbegin(); ri != st[b].rend(); ri++) {
        int x = (*ri).second, v = (*ri).first; 
        auto it = st[b].upper_bound({v + k, 1000000000}); 
        if (it == st[b].end()) {
            f[x] = 1; 
            g[x] = v + k; 
        } else {
            int y = (*it).second; 
            f[x] = f[y] + 1; 
            g[x] = g[y]; 
        }
    }
}
 
void dbg(int b) {
    cout << "Block B: " << b << '\n';
    for (auto [v, x]: st[b]) {
        cout << "! " << x << "  val " << v << '\n';
        cout << f[x] << ' ' << g[x] << '\n'; 
    }
    cout << '\n';
}
 
void reset() {
    for (int i = 0; i < B; ++i) st[i].clear(); 
 
    vector<pair<int, int>> p; 
    for (int i = 0; i < n; ++i) p.push_back({a[i], i}); 
    sort(p.begin(), p.end()); 
    
    for (int i = 0; i < n; ++i) {
        st[i / S].insert(p[i]); 
    }
 
    for (int i = 0; i < B; ++i) updb(i); 
}
 
int update(int p, int nv) {
    int ov = a[p]; 
    a[p] = nv; 
    for (int i = 0; i < B; ++i) {
        if (st[i].find({ov, p}) != st[i].end()) {
            // cout << "erase block " << i << ' ' << p << '\n';
            st[i].erase({ov, p}); 
            updb(i); 
        }
    }
 
    for (int i = 0; i < B; ++i) {
        if ((st[i].size() && ((*st[i].rbegin()).first >= nv)) || (i + 1 == B)) {
            // cout << "insert into " << i << '\n';
            st[i].insert({nv, p}); 
            updb(i); 
            break; 
        }
    }
    // dbg(0); 
    // dbg(387); 
 
    for (int i = 0; i < B; ++i) {
        if ((int)st[i].size() > 2 * S) {
            reset(); 
            break; 
        }
    }
 
    int ans = 0; 
    int last = -2e9; 

    for (int i = 0; i < B; ++i) {
        if (!st[i].size()) continue; 
        if ((*st[i].rbegin()).first <= last) continue; 
        int x = (*st[i].upper_bound({last, 1000000000})).second; 
        ans += f[x]; 
        last = g[x]; 
    }
 
    // for (int i = 0; i < n; ++i) {
    //     cout << a[i] << " \n"[i == n - 1]; 
    // }
    return ans; 
}   
 
 
void init(int N, int L, int X[]) {
    n = N; 
    k = L; 
    for (int i = 0; i < N; ++i) {
        a[i] = X[i]; 
    }
    reset(); 
}
 
// int main() {
//     int N, L; 
//     cin >> N >> L; 
//     int A[N]; 
//     for (int i = 0; i < N; ++i) {
//         cin >> A[i]; 
//     }
//     init(N, L, A); 
//     int Q; 
//     cin >> Q; 
//     while (Q--) {
//         int X, Y; 
//         cin >> X >> Y; 
//         cout << update(X, Y) << "\n";
//     }
// }

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Incorrect 17 ms 9308 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Incorrect 17 ms 9308 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Incorrect 17 ms 9308 KB Output isn't correct
8 Halted 0 ms 0 KB -