oj.uz

Submission #115764

# Submission time Handle Problem Language Result Execution time Memory
115764 2019-06-09T00:48:45 Z songc Dancing Elephants (IOI11_elephants) C++14
26 / 100
 19 ms 1784 KB 
#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;
    }
};
Eleph B[400][400];
int sz[400];

void calc(int t){
    int k=sz[t]-1;
    for (int j=k; j>=0; j--){
        while (B[t][j].x + K < B[t][k].x) k--;
        if (k == sz[t]-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][sz[i/Sq]++].x = X[i];
        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 (sz[k] == 0) continue;
        if (lower_bound(B[k], B[k]+sz[k], (Eleph){x, 0, 0})->x == x) break;
    }
    sz[k]--;
    for (int i=lower_bound(B[k], B[k]+sz[k], (Eleph){x, 0, 0}) - B[k]; i<sz[k]; i++){
        B[k][i] = B[k][i+1];
    }
    calc(k);
}

void add(int x){
    int k;
    for (k=0; k<M-1; k++){
        if (sz[k] == 0) continue;
        if (lower_bound(B[k], B[k]+sz[k], (Eleph){x, 0, 0}) != B[k]+sz[k]) break;
    }
    B[k][sz[k]++] = (Eleph){x, 0, 0};
    for (int i=sz[k]-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;
            sz[i] = 0;
        }
        init(N, K, T);
    }

    int p=-1, ans=0;
    for (int i=0; i<M; i++){
        if (sz[i] == 0) continue;
        int k = upper_bound(B[i], B[i]+sz[i], (Eleph){p, 0, 0}) - B[i];
        if (k == sz[i]) continue;
        ans += B[i][k].s;
        p = B[i][k].p;
    }
    return ans;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
0 / 24.0

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

Subtask #4
0 / 47.0

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

Subtask #5
0 / 3.0

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