oj.uz

답안 #110367

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
110367 2019-05-10T18:19:22 Z doowey 코끼리 (Dancing Elephants) (IOI11_elephants) C++14
26 / 100
 9000 ms 4776 KB 
#include <bits/stdc++.h>
#include "elephants.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

const int MAXN = 150004;
const int B = 1000;

struct Data{
    int pos;
    int jumpl;
    int nexp;
    bool operator<(const Data &D) const {
        return pos < D.pos;
    }
};

vector<Data> Q[MAXN];
int n;
int bl;
int len;

void compute(int id){
    if(Q[id].empty())
        return;
    sort(Q[id].begin(), Q[id].end());
    int sz = Q[id].size();
    int lp = sz - 1;
    for(int i = sz - 1; i >= 0 ; i -- ){
        while(Q[id][lp].pos - Q[id][i].pos > len){
            -- lp;
        }
        if(lp == sz - 1){
            Q[id][i].jumpl = 1;
            Q[id][i].nexp = Q[id][i].pos + len;
        }
        else{
            Q[id][i].jumpl = Q[id][lp + 1].jumpl + 1;
            Q[id][i].nexp = Q[id][lp + 1].nexp;
        }
    }
}

int pz[MAXN];

int oper = 1;

void init(int N, int L, int X[]){
    n = N;
    len = L;
    bl = (n + B - 1) / B;
    for(int i = 0 ; i < n ; i ++ )
        pz[i] = X[i];
    for(int i = 0 ; i < n ; i ++ ){
        Q[i/B].push_back({X[i], -1, -1});
    }
    for(int i = 0 ; i < bl ; i ++ )
        compute(i);
}

void Erase(int el){
    int id = -1;
    for(int i = bl - 1; i >= 0 ; i -- ){
        if(Q[i].empty())continue;
        if(el >= Q[i][0].pos){
            id = i;
            break;
        }
    }
    vector<int> idx;
    bool er = false;
    for(auto p : Q[id]){
        if(p.pos == el){
            if(er){
                idx.push_back(p.pos);
            }
            else{
                er=true;
            }
        }
        else{
            idx.push_back(p.pos);
        }
    }
    Q[id].clear();
    for(auto v : idx){
        Q[id].push_back({v, -1, -1});
    }
    compute(id);
}

void Insert(int el){
    int id = 0;
    for(int i = bl - 1; i >= 0 ; i -- ){
        if(Q[i].empty()) continue;
        if(el >= Q[i][0].pos){
            id = i;
            break;
        }
    }
    Q[id].push_back({el, -1, -1});
    compute(id);
}

int update(int i, int y){
    oper ++ ;
    oper %= B;
    if(oper == 0){
        for(int j = 0 ; j < bl ; j ++ ) Q[j].clear();
        for(int j = 0 ; j < n ; j ++ ) Q[j / B].push_back({pz[j], -1, -1});
        for(int j = 0 ; j < bl; j ++ ) compute(j);
    }
    Erase(pz[i]);
    pz[i]=y;
    Insert(pz[i]);
    int endp = -1;
    int res = 0;
    int rd;
    Data C;
    for(int j = 0 ; j < bl ; j ++ ){
        if(Q[j].empty())
            continue;
        C = {endp, -1, -1};
        rd = upper_bound(Q[j].begin(), Q[j].end(), C) - Q[j].begin();
        if(rd < Q[j].size()){
            res += Q[j][rd].jumpl;
            endp = Q[j][rd].nexp;
        }
    }
    for(int j = 0 ; j < bl ; j ++ ){
        compute(j);
    }
    return res;
}

Compilation message

elephants.cpp: In function 'int update(int, int)':
elephants.cpp:132:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(rd < Q[j].size()){
            ~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 3916 KB Output is correct
2 Correct 6 ms 3840 KB Output is correct
3 Correct 5 ms 3840 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 3916 KB Output is correct
2 Correct 6 ms 3840 KB Output is correct
3 Correct 5 ms 3840 KB Output is correct
4 Correct 6 ms 3840 KB Output is correct
5 Correct 7 ms 3840 KB Output is correct
6 Correct 6 ms 3840 KB Output is correct

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 3916 KB Output is correct
2 Correct 6 ms 3840 KB Output is correct
3 Correct 5 ms 3840 KB Output is correct
4 Correct 6 ms 3840 KB Output is correct
5 Correct 7 ms 3840 KB Output is correct
6 Correct 6 ms 3840 KB Output is correct
7 Execution timed out 9021 ms 4776 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 3916 KB Output is correct
2 Correct 6 ms 3840 KB Output is correct
3 Correct 5 ms 3840 KB Output is correct
4 Correct 6 ms 3840 KB Output is correct
5 Correct 7 ms 3840 KB Output is correct
6 Correct 6 ms 3840 KB Output is correct
7 Execution timed out 9021 ms 4776 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 3916 KB Output is correct
2 Correct 6 ms 3840 KB Output is correct
3 Correct 5 ms 3840 KB Output is correct
4 Correct 6 ms 3840 KB Output is correct
5 Correct 7 ms 3840 KB Output is correct
6 Correct 6 ms 3840 KB Output is correct
7 Execution timed out 9021 ms 4776 KB Time limit exceeded
8 Halted 0 ms 0 KB -