#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#include "camera.h"
#include <bits/stdc++.h>
using namespace std;
using ari2 = array<int, 2>;
#define vt vector
#define size(x) (int(x.size()))
#define all(x) begin(x), end(x)
#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)
#define chmax(a, b) a = a > (b) ? a : (b)
#define chmin(a, b) a = a < (b) ? a : (b)
static constexpr int mxN = 150005, B = 388;
static int N, L, pos[mxN];
static ari2 A[mxN];
static vt<array<int, 5>> blocks[B]; // position, index, next block, next index, value to add
static vt<ari2> endss;
void fix() {
ROF(i, size(endss)-1, 1)
if (endss[i] < endss[i-1])
swap(endss[i], endss[i-1]);
}
static void upd(int b, bool added) {
if (!size(blocks[b]))
return;
if (added)
ROF(i, size(blocks[b])-1, 1)
if (blocks[b][i][0] < blocks[b][i-1][0])
swap(blocks[b][i], blocks[b][i-1]);
endss.push_back({blocks[b].back()[0], b});
fix();
int j = size(blocks[b]) - 1;
ROF(i, size(blocks[b])-1, 0) {
if (blocks[b].back()[0] <= blocks[b][i][0] + L) {
blocks[b][i][2] = blocks[b][i][3] = blocks[b][i][4] = B;
continue;
}
while (blocks[b][j-1][0] > blocks[b][i][0] + L)
j--;
blocks[b][i] = {
blocks[b][i][0], blocks[b][i][1], b,
blocks[b][j][2] == b ? blocks[b][j][3] : j,
blocks[b][j][2] == b ? blocks[b][j][4] + 1 : 1
};
}
}
static void recalc() {
int cur = 0;
FOR(i, 0, (N-1)/B)
FOR(j, 0, size(blocks[i])-1)
A[cur++] = {blocks[i][j][0], blocks[i][j][1]};
FOR(i, 0, (N-1)/B) {
blocks[i].clear();
int n = min(N, (i+1)*B);
FOR(j, i*B, n-1) {
blocks[i].push_back({A[j][0], A[j][1], B, B, B});
pos[A[j][1]] = i;
}
}
endss.clear();
ROF(b, (N-1)/B, 0)
upd(b, false);
}
void init(int _N, int _L, int X[]) {
N = _N, L = _L;
FOR(i, 0, N-1)
blocks[0].push_back({X[i], i, B, B, B});
recalc();
}
static int it_cnt;
int update(int ind, int y) {
int &p = pos[ind];
FOR(i, 0, size(blocks[p])-1) {
if (blocks[p][i][1] == ind) {
if (i == size(blocks[p])-1) {
endss.erase(find(all(endss), ari2{blocks[p][i][0], p}));
if (i) {
endss.push_back({blocks[p][i-1][0], p});
fix();
}
}
blocks[p].erase(begin(blocks[p]) + i);
break;
}
}
int it = lower_bound(all(endss), ari2{y, 0}) - begin(endss);
it -= it == size(endss);
int np = endss[it][1];
endss.erase(begin(endss) + it);
blocks[np].push_back({y, ind, B, B, B});
if (size(blocks[p]) && p != np)
endss.erase(find(all(endss), ari2{blocks[p].back()[0], p}));
if (p < np) {
upd(np, true);
upd(p, false);
} else if (p > np) {
upd(p, false);
upd(np, true);
} else {
upd(p, true);
}
p = np; // lol
if (++it_cnt % B == 0)
recalc();
int cb = endss[0][1], ce = 0, ret = 0;
while (cb < B) {
if (blocks[cb][ce][2] != cb) {
int it_r = lower_bound(all(endss), ari2{blocks[cb][ce][0]+L+1, 0}) - begin(endss);
int r = it_r < size(endss) ? endss[it_r][1] : B;
int rr = r == B ? 0 : lower_bound(all(blocks[r]), array<int, 5>{blocks[cb][ce][0]+L+1, 0, 0, 0, 0}) - begin(blocks[r]);
blocks[cb][ce] = {blocks[cb][ce][0], blocks[cb][ce][1], r, rr, 1};
}
ret += blocks[cb][ce][4];
int nb = blocks[cb][ce][2], ne = blocks[cb][ce][3];
cb = nb, ce = ne;
}
return ret;
}
Compilation message
elephants.cpp:3:10: fatal error: camera.h: No such file or directory
3 | #include "camera.h"
| ^~~~~~~~~~
compilation terminated.
