oj.uz

답안 #115684

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
115684 2019-06-08T15:48:24 Z songc 코끼리 (Dancing Elephants) (IOI11_elephants) C++14
50 / 100
 9000 ms 6652 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;
int A[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});
        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);

    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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 128 ms 2168 KB Output is correct
8 Correct 170 ms 2532 KB Output is correct
9 Correct 284 ms 3604 KB Output is correct
10 Correct 4248 ms 4472 KB Output is correct
11 Correct 4268 ms 4400 KB Output is correct
12 Correct 4417 ms 4176 KB Output is correct
13 Correct 4493 ms 4216 KB Output is correct

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 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 128 ms 2168 KB Output is correct
8 Correct 170 ms 2532 KB Output is correct
9 Correct 284 ms 3604 KB Output is correct
10 Correct 4248 ms 4472 KB Output is correct
11 Correct 4268 ms 4400 KB Output is correct
12 Correct 4417 ms 4176 KB Output is correct
13 Correct 4493 ms 4216 KB Output is correct
14 Correct 3822 ms 4464 KB Output is correct
15 Correct 300 ms 3320 KB Output is correct
16 Correct 602 ms 4344 KB Output is correct
17 Correct 2101 ms 6076 KB Output is correct
18 Correct 4216 ms 6060 KB Output is correct
19 Execution timed out 9046 ms 6652 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 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 128 ms 2168 KB Output is correct
8 Correct 170 ms 2532 KB Output is correct
9 Correct 284 ms 3604 KB Output is correct
10 Correct 4248 ms 4472 KB Output is correct
11 Correct 4268 ms 4400 KB Output is correct
12 Correct 4417 ms 4176 KB Output is correct
13 Correct 4493 ms 4216 KB Output is correct
14 Correct 3822 ms 4464 KB Output is correct
15 Correct 300 ms 3320 KB Output is correct
16 Correct 602 ms 4344 KB Output is correct
17 Correct 2101 ms 6076 KB Output is correct
18 Correct 4216 ms 6060 KB Output is correct
19 Execution timed out 9046 ms 6652 KB Time limit exceeded
20 Halted 0 ms 0 KB -