제출 #367679

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
367679		ijxjdjd	코끼리 (Dancing Elephants) (IOI11_elephants)	C++14	50 / 100	9074 ms	4132 KiB

elephants

using namespace std;

#include "elephants.h"
#include <bits/stdc++.h>
//
//#pragma GCC optimize ("Ofast")
//#pragma GCC target ("avx2")

#define f first
#define s second
#define all(x) begin(x), end(x)
const int MAXN = 150000;
int N;
int BLOCKSIZE;
int L;
const int K = 550;
int REDO = K;
vector<vector<int>> blocks;
vector<vector<pair<int, int>>> storeBack;
vector<int> permVec;
int X[MAXN];
int blockId[MAXN];


void recalcBlock(int i, bool needSort) {
    if (blocks[i].size() == 0) {
        return;
    }
    auto comp = [&] (const int& lhs, const int& rhs) {
    return X[lhs] < X[rhs];
    };
    if (needSort) {
        sort(all(blocks[i]), comp);
    }
    storeBack[i].resize(blocks[i].size());
    int l = blocks[i].size()-1;
    int r = blocks[i].size()-1;
    while (l >= 0) {
        while (X[blocks[i][l]] + L < X[blocks[i][r]]) {
            r--;
        }
        if (r == blocks[i].size()-1) {
            storeBack[i][l] = {1, X[blocks[i][l]] + L};
        }
        else {
            storeBack[i][l] = storeBack[i][r+1];
            storeBack[i][l].f++;
        }
        l--;
    }
}
void rebuild() {
    for (auto& vec : blocks) {
        vec.clear();
    }
    auto comp = [&] (const int& lhs, const int& rhs) {
        return X[lhs] < X[rhs];
    };
    sort(all(permVec), comp);
    for (int i = 0; i < N; i++) {
        blocks[i/K].push_back(permVec[i]);
        blockId[permVec[i]] = i/K;
    }
    for (int i = 0; i < BLOCKSIZE; i++) {
        recalcBlock(i, false);
    }
}
int getAns() {
    int next = -1;
    int res = 0;
    for (int i = 0; i < BLOCKSIZE; i++) {
        if (blocks[i].size() > 0 && next < X[blocks[i].back()]) {
            int low = 0;
            int high = blocks[i].size()-1;
            while (low < high) {
                int mid = (low + high)/2;
                if (next < X[blocks[i][mid]]) {
                    high = mid;
                }
                else {
                    low = mid+1;
                }
            }
            res += storeBack[i][high].f;
            next = storeBack[i][high].s;
        }
    }
    return res;
}
void init(int n, int l, int LD[])
{
  N = n;
  L = l;
  for (int i = 0; i < N; i++) {
    permVec.push_back(i);
    X[i] = LD[i];
  }
  BLOCKSIZE = (N-1)/K + 1;
  blocks.resize(BLOCKSIZE, {});
  storeBack.resize(BLOCKSIZE, {});
  rebuild();
}

int update(int i, int y)
{
    if (REDO == 0) {
        rebuild();
        REDO = 3*K;
    }
    X[i] = y;
    blocks[blockId[i]].erase(find(all(blocks[blockId[i]]), i));
    recalcBlock(blockId[i], false);
    for (int j = 0; j < BLOCKSIZE; j++) {
        if ((j == BLOCKSIZE - 1) || (blocks[j].size() > 0 && X[blocks[j].back()] >= y)) {
            blocks[j].push_back(i);
            blockId[i] = j;
            recalcBlock(j, true);
            break;
        }
    }
    REDO--;
    return getAns();
}

컴파일 시 표준 에러 (stderr) 메시지

elephants.cpp: In function 'void recalcBlock(int, bool)':
elephants.cpp:42:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         if (r == blocks[i].size()-1) {
      |             ~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3