| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 541353 | akhan42 | Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define F first
#define S second
#define forn(i, n) for(int i = 0; i < n; ++i)
#define forbn(i, b, n) for(int i = b; i < n; ++i)
#define sz(v) (int)v.size()
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define min3(a, b, c) min(a, min(b, c))
#define max3(a, b, c) max(a, max(b, c))
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long long ll;
typedef complex<double> cd; // !!! long double slow
template <class T> inline void mineq(T &a, T b) { a = min(a, b); }
template <class T> inline void maxeq(T &a, T b) { a = max(a, b); }
int n, Q;
const int MXd2 = 1000 * 1000;
const int MX = 2 * MXd2;
int ol[MX], oright[MX];
vector<bool> ans(MXd2, true);
vii mx2vq[MXd2];
vii v2mxq[MX];
int Ks[MX];
vi vals;
vi a;
bool cmp(int v1, int v2) {
return ol[v1] < ol[v2];
}
struct Seg {
int mx[MX], t[MX];
vi sl[MX];
Seg() {
for(int p = n; p < 2 * n; p++) {
mx[p] = a[p - n];
sl[p].reserve(1);
sl[p].pb(a[p - n]);
t[p] = -1;
oright[p] = ol[p] = p - n;
}
for(int p = n - 1; p > 0; p--) {
ol[p] = min(ol[2 * p], ol[2 * p + 1]);
oright[p] = max(oright[2 * p], oright[2 * p + 1]);
mx[p] = max(mx[2 * p], mx[2 * p + 1]);
t[p] = max(t[2 * p], t[2 * p + 1]);
sl[p].reserve(sz(sl[2 * p]) + sz(sl[2 * p + 1]));
merge(all(sl[2 * p]), all(sl[2 * p + 1]), back_inserter(sl[p]));
int ind = lower_bound(all(sl[2 * p + 1]), mx[2 * p]) - sl[2 * p + 1].begin();
if(ind != 0)
maxeq(t[p], vals[mx[2 * p]] + vals[sl[2 * p + 1][ind - 1]]);
}
forbn(p, 1, n)
vi().swap(sl[p]);
}
void query(int l, int r, int k, int left_max, int q) {
vi vert;
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) {
vert.pb(l++);
}
if (r & 1) {
vert.pb(--r);
}
}
sort(all(vert), cmp);
for(int v: vert) {
if(t[v] > k) {
ans[q] = false;
return;
}
if(left_max != -1) {
mx2vq[left_max].eb(v, q);
}
maxeq(left_max, mx[v]);
}
}
void process() {
for(int lm = sz(vals) - 1; lm >= 0; --lm) {
if(lm != sz(vals) - 1)
vii().swap(mx2vq[lm + 1]);
for(ii p: mx2vq[lm]) {
if(ans[p.S])
v2mxq[p.F].eb(lm, p.S);
}
}
vii().swap(mx2vq[0]);
for(int p = 2 * n - 1; p > 0; p--) {
if(p < n) {
sl[p].reserve(sz(sl[2 * p]) + sz(sl[2 * p + 1]));
merge(all(sl[2 * p]), all(sl[2 * p + 1]), back_inserter(sl[p]));
vi().swap(sl[2 * p]);
vi().swap(sl[2 * p + 1]);
}
else {
sl[p].reserve(1);
sl[p].pb(a[p - n]);
}
int x = sz(sl[p]) - 1;
forn(w, sz(v2mxq[p])) {
int lm = v2mxq[p][w].F, q = v2mxq[p][w].S;
int k = Ks[q];
if(!ans[q])
continue;
while(x >= 0 && sl[p][x] >= lm)
x--;
if(x < 0)
break;
if(vals[sl[p][x]] >= k - vals[lm] + 1) {
ans[q] = false;
}
}
vii().swap(v2mxq[p]);
}
}
};
int v2c(int v) {
return lower_bound(all(vals), v) - vals.begin();
}
void solve() {
cin >> n >> Q;
a.resize(n);
forn(i, n) {
cin >> a[i];
vals.pb(a[i]);
}
sort(all(vals));
vals.erase(unique(all(vals)), vals.end());
forn(i, n)
a[i] = v2c(a[i]);
Seg seg;
int QQ = Q / 4;
forn(q, Q) {
int l, r, k;
cin >> l >> r >> k;
l--; r--;
Ks[q] = k;
seg.query(l, r, k, -1, q);
if(q == QQ || q == 2 * QQ || q == 3 ** QQ)
seg.process();
}
seg.process();
forn(i, Q) {
cout << ans[i] << '\n';
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// freopen("boards.in", "r", stdin);
// freopen("boards.out", "w", stdout);
int t = 1;
// cin >> t;
while(t--) {
solve();
}
}