Submission #115766

#	Time	Username	Problem	Language	Result	Execution time	Memory
115766		songc	Dancing Elephants (IOI11_elephants)	C++14	26 / 100	534 ms	4472 KiB

elephants

#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
 
int N, K, Sq, M, Q;
int A[150505];
int T[150505];
 
struct Eleph{
    int x, s, p;
    bool operator<(const Eleph &r)const{
        return x < r.x;
    }
};
vector<Eleph> B[400];
 
void calc(int t){
    int k=B[t].size()-1;
    for (int j=k; j>=0; j--){
        while (B[t][j].x + K < B[t][k].x) k--;
        if (k == (int)B[t].size()-1) B[t][j].s = 1, B[t][j].p = B[t][j].x + K;
        else B[t][j].s = B[t][k+1].s + 1, B[t][j].p = B[t][k+1].p;
    }
}
 
void init(int n, int l, int X[]){
    N=n, K=l;
    Sq = sqrt(N);
    M = (N+Sq-1)/Sq;
    for (int i=0; i<N; i++) {
        B[i/Sq].push_back({X[i], 0, 0});
        if (!Q) A[i] = X[i];
    }
    for (int i=0; i<M; i++) calc(i);
}
 
void del(int x){
    int k;
    for (k=0; k<M; k++) {
        if (B[k].empty()) continue;
        if (lower_bound(B[k].begin(), B[k].end(), (Eleph){x, 0, 0})->x == x) break;
    }
    B[k].erase(lower_bound(B[k].begin(), B[k].end(), (Eleph){x, 0, 0}));
    calc(k);
}
 
void add(int x){
    int k;
    for (k=0; k<M-1; k++){
        if (B[k].empty()) continue;
        if (lower_bound(B[k].begin(), B[k].end(), (Eleph){x, 0, 0}) != B[k].end()) break;
    }
    B[k].push_back({x, 0, 0});
    for (int i=(int)B[k].size()-1; i>0; i--){
        if (B[k][i-1].x > B[k][i].x) swap(B[k][i], B[k][i-1]);
    }
    calc(k);
}
 
int update(int i, int y){
    del(A[i]);
    A[i] = y;
    add(y);
    Q++;
 
    if (Q % 400 == 0){
        int t=0;
        for (int i=0; i<M; i++) {
            for (Eleph it : B[i]) T[t++] = it.x;
            B[i].clear();
        }
        init(N, K, T);
    }
 
    int p=-1, ans=0;
    for (int i=0; i<M; i++){
        if (B[i].empty()) continue;
        int k = upper_bound(B[i].begin(), B[i].end(), (Eleph){p, 0, 0}) - B[i].begin();
        if (k == (int)B[i].size()) continue;
        ans += B[i][k].s;
        p = B[i][k].p;
    }
    return ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3