oj.uz

Submission #115761

# Submission time Handle Problem Language Result Execution time Memory
115761 2019-06-09T00:17:24 Z songc Dancing Elephants (IOI11_elephants) C++14
50 / 100
 813 ms 5084 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], 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; i<N; i++) T[i] = A[i];
        for (int i=0; i<M; i++) B[i].clear();
        sort(T, T+N);
        init(N, K, T);
    }

    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 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
24.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 Correct 166 ms 2208 KB Output is correct
8 Correct 222 ms 2688 KB Output is correct
9 Correct 397 ms 3576 KB Output is correct
10 Correct 584 ms 3628 KB Output is correct
11 Correct 563 ms 3448 KB Output is correct
12 Correct 813 ms 3772 KB Output is correct
13 Correct 534 ms 3320 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 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 Correct 166 ms 2208 KB Output is correct
8 Correct 222 ms 2688 KB Output is correct
9 Correct 397 ms 3576 KB Output is correct
10 Correct 584 ms 3628 KB Output is correct
11 Correct 563 ms 3448 KB Output is correct
12 Correct 813 ms 3772 KB Output is correct
13 Correct 534 ms 3320 KB Output is correct
14 Runtime error 101 ms 5084 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 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 Correct 166 ms 2208 KB Output is correct
8 Correct 222 ms 2688 KB Output is correct
9 Correct 397 ms 3576 KB Output is correct
10 Correct 584 ms 3628 KB Output is correct
11 Correct 563 ms 3448 KB Output is correct
12 Correct 813 ms 3772 KB Output is correct
13 Correct 534 ms 3320 KB Output is correct
14 Runtime error 101 ms 5084 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -