Submission #975326

#	Time	Username	Problem	Language	Result	Execution time	Memory
975326		fzyzzz_z	Dancing Elephants (IOI11_elephants)	C++17	Compilation error	0 ms	0 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 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";
    }
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccDJHOl3.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccXGroY5.o:elephants.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status