| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1256863 | christhegamechanger | 축제 (IOI25_festival) | C++17 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
namespace Solver {
// Constants
static const int MAXV = 11; // values 0..10
// Globals
int N, M;
vector<int> Trow, Hcol;
// RMQ (min on H)
vector<int> lg2;
vector<vector<int>> st; // st[k][i] = min on [i, i+2^k-1]
// For every threshold t, nearest barrier with H >= t
vector<vector<int>> prevGE, nextGE; // size [11][M]
// prefix min/max for T
vector<int> prefMinT, prefMaxT;
// last index r with prefMinT[r] > h, for h=0..10
int lastGreater[ MAXV ];
inline int rmqMinH(int l, int r) {
if (l > r) return INT_MAX;
int len = r - l + 1;
int k = lg2[len];
return min(st[k][l], st[k][r - (1 << k) + 1]);
}
inline pair<int,int> component_bounds(int L, int R, int S, int t) {
// maximal contiguous block around S inside [L,R] with H < t
int Lb = prevGE[t][S] + 1;
if (Lb < L) Lb = L;
int Rb = nextGE[t][S] - 1;
if (Rb > R) Rb = R;
return {Lb, Rb};
}
void initialize(vector<int> T, vector<int> H) {
Trow = move(T);
Hcol = move(H);
N = (int)Trow.size();
M = (int)Hcol.size();
// Build RMQ (sparse table) on H
lg2.assign(M + 1, 0);
for (int i = 2; i <= M; ++i) lg2[i] = lg2[i >> 1] + 1;
int K = lg2[M];
st.assign(K + 1, vector<int>(M));
for (int i = 0; i < M; ++i) st[0][i] = Hcol[i];
for (int k = 1; k <= K; ++k) {
int len = 1 << k, half = len >> 1;
for (int i = 0; i + len - 1 < M; ++i) {
st[k][i] = min(st[k-1][i], st[k-1][i + half]);
}
}
// prevGE / nextGE for each threshold t = 0..10
prevGE.assign(MAXV, vector<int>(M));
nextGE.assign(MAXV, vector<int>(M));
for (int t = 0; t < MAXV; ++t) {
int last = -1;
for (int j = 0; j < M; ++j) {
prevGE[t][j] = last;
if (Hcol[j] >= t) last = j;
}
last = M;
for (int j = M - 1; j >= 0; --j) {
nextGE[t][j] = last;
if (Hcol[j] >= t) last = j;
}
}
// prefix min/max of T
prefMinT.assign(N, 0);
prefMaxT.assign(N, 0);
for (int i = 0; i < N; ++i) {
if (i == 0) {
prefMinT[i] = Trow[i];
prefMaxT[i] = Trow[i];
} else {
prefMinT[i] = min(prefMinT[i-1], Trow[i]);
prefMaxT[i] = max(prefMaxT[i-1], Trow[i]);
}
}
// lastGreater[h]: last r with prefMinT[r] > h
for (int h = 0; h < MAXV; ++h) {
int last = -1;
for (int r = 0; r < N; ++r) if (prefMinT[r] > h) last = r;
lastGreater[h] = last; // may be -1 if nothing > h
}
}
bool can_reach(int L, int R, int S, int D) {
if (S == D) return true; // trivial
int tcur = Trow[0]; // current horizontal ability
auto seg = component_bounds(L, R, S, tcur);
int Lb = seg.first, Rb = seg.second;
if (D >= Lb && D <= Rb) return true;
// Iterate while we can increase tcur using the best "elevator" column inside [Lb,Rb]
for (int iter = 0; iter < 15; ++iter) { // 15 > MAXV, safe guard
int hmin = rmqMinH(Lb, Rb); // best (smallest) humidity we can touch now
int rmax = (hmin >= 0 && hmin < MAXV) ? lastGreater[hmin] : -1;
if (rmax < 0) return false; // cannot go down at all (shouldn't happen due to guarantees)
int tnew = prefMaxT[rmax]; // best row temperature reachable via that elevator
if (tnew <= tcur) return false; // no more expansion possible
tcur = tnew;
seg = component_bounds(L, R, S, tcur);
Lb = seg.first; Rb = seg.second;
if (D >= Lb && D <= Rb) return true;
}
return false; // should not reach here
}
} // namespace Solver
// ----- If the judge uses the two-function interface, keep only these: -----
void initialize(std::vector<int> T, std::vector<int> H) {
Solver::initialize(move(T), move(H));
}
bool can_reach(int L, int R, int S, int D) {
return Solver::can_reach(L, R, S, D);
}
// ----- Sample grader (as trong PDF): keep for local test; remove if not needed -----
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M;
if (!(cin >> N >> M)) return 0;
vector<int> T(N), H(M);
for (int i = 0; i < N; ++i) cin >> T[i];
for (int j = 0; j < M; ++j) cin >> H[j];
initialize(T, H);
int Q; cin >> Q;
while (Q--) {
int L, R, S, D;
cin >> L >> R >> S >> D;
cout << (can_reach(L, R, S, D) ? 1 : 0) << '\n';
}
return 0;
}