제출 #975323

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
975323		fzyzzz_z	코끼리 (Dancing Elephants) (IOI11_elephants)	C++17	26 / 100	14 ms	10308 KiB

elephants

#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 s[B + 10], f[B + 10], g[B + 10]; 
set<pair<int, int>> st[B + 10]; 

void upds() {
    int f = 0, last; 

    for (int i = 0; i < B; ++i) {
        if (!f) {
            s[i] = -1; 
            if (st[i].size()) {
                f = 1; 
                s[i] = (*st[i].begin()).second; 
                last = g[s[i]]; 
            }
            continue; 
        }
        if (!st[i].size()) {
            s[i] = -1; 
        } else if ((*st[i].rbegin()).first <= last) {
            s[i] = -1; 
        } else {
            int next = (*st[i].upper_bound({last, 1000000000})).second; 
            s[i] = next; 
            last = g[next]; 
        }
    }
}
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); 
    upds(); 
}

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; 
        }
    }

    upds(); 
    int ans = 0; 
    for (int i = 0; i < B; ++i) {
        if (s[i] != -1) {
            ans += f[s[i]]; 
            // cout << "! " << i << ' ' << s[i] << '\n';
            // cout << f[s[i]] << "\n";
        }
    }

    // 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 / 10
• Subtask 2: 16 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3