| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 367674 | ijxjdjd | 코끼리 (Dancing Elephants) (IOI11_elephants) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
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 = 500;
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 = 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();
}