oj.uz

Submission #115690

# Submission time Handle Problem Language Result Execution time Memory
115690 2019-06-08T16:04:39 Z songc Dancing Elephants (IOI11_elephants) C++14
50 / 100
 456 ms 3704 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;
    }
};
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-1; k++) if (x < B[k+1][0].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 (x < B[k+1][0].x) 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){
        for (int i=0, t=0; i<M; i++) {
            for (Eleph it : B[i]) T[t++] = it.x;
            B[i].clear();
        }
        for (int i=0; i<N; i++) B[i/Sq].push_back({T[i], 0, 0});
        for (int i=0; i<M; i++) calc(i);
    }

    int p=-1, ans=0;
    for (int i=0; i<M; i++){
        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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 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 3 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
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 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 Correct 165 ms 1332 KB Output is correct
8 Correct 200 ms 1596 KB Output is correct
9 Correct 348 ms 2292 KB Output is correct
10 Correct 330 ms 2296 KB Output is correct
11 Correct 357 ms 2388 KB Output is correct
12 Correct 456 ms 2296 KB Output is correct
13 Correct 308 ms 2168 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 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 Correct 165 ms 1332 KB Output is correct
8 Correct 200 ms 1596 KB Output is correct
9 Correct 348 ms 2292 KB Output is correct
10 Correct 330 ms 2296 KB Output is correct
11 Correct 357 ms 2388 KB Output is correct
12 Correct 456 ms 2296 KB Output is correct
13 Correct 308 ms 2168 KB Output is correct
14 Runtime error 92 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 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 3 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 Correct 165 ms 1332 KB Output is correct
8 Correct 200 ms 1596 KB Output is correct
9 Correct 348 ms 2292 KB Output is correct
10 Correct 330 ms 2296 KB Output is correct
11 Correct 357 ms 2388 KB Output is correct
12 Correct 456 ms 2296 KB Output is correct
13 Correct 308 ms 2168 KB Output is correct
14 Runtime error 92 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -