Submission #541335

#TimeUsernameProblemLanguageResultExecution timeMemory
541335akhan42Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++17
0 / 100
484 ms262144 KiB
#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 INF = 1000 * 1000 * 1000 + 10; const int MX = 2 * 1000 * 1000; int ol[MX]; bool cmp(int v1, int v2) { return ol[v1] < ol[v2]; } struct Seg { int mx[MX], t[MX]; int* sl[MX]; int razmer[MX]; Seg(vi& a) { for(int p = n; p < 2 * n; p++) { mx[p] = a[p - n]; t[p] = -INF; ol[p] = p - n; razmer[p] = 1; sl[p] = new int[razmer[p]]; sl[p][0] = a[p - n]; } for(int p = n - 1; p > 0; p--) { ol[p] = min(ol[2 * p], ol[2 * p + 1]); mx[p] = max(mx[2 * p], mx[2 * p + 1]); t[p] = max(t[2 * p], t[2 * p + 1]); razmer[p] = razmer[2 * p] + razmer[2 * p + 1]; sl[p] = new int[razmer[p]]; merge(sl[2 * p], sl[2 * p] + razmer[2 * p], sl[2 * p + 1], sl[2 * p + 1] + razmer[2 * p + 1], sl[p]); int ind = lower_bound(sl[2 * p + 1], sl[2 * p + 1] + razmer[2 * p + 1], mx[2 * p]) - sl[2 * p + 1]; if(ind != 0) maxeq(t[p], mx[2 * p] + sl[2 * p + 1][ind - 1]); } forbn(p, 1, 2 * n) { delete sl[p]; } } bool query(int l, int r, int k, int left_max) { 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); bool ans = true; for(int v: vert) { ans = ans && t[v] <= k; int rp = left_max - 1, lp = k - left_max + 1; if(lp <= rp) { int indl = lower_bound(sl[v], sl[v] + razmer[v], lp) - sl[v]; int indr = lower_bound(sl[v], sl[v] + razmer[v], rp + 1) - sl[v]; ans = ans && indl == indr; } if(!ans) return ans; maxeq(left_max, mx[v]); } return ans; } }; void solve() { cin >> n >> q; vi a(n); forn(i, n) cin >> a[i]; Seg seg(a); forn(_, q) { int l, r, k; cin >> l >> r >> k; l--; r--; auto ans = seg.query(l, r, k, -INF); cout << ans << '\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(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...