Submission #595219

#TimeUsernameProblemLanguageResultExecution timeMemory
595219tamthegodHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++14
100 / 100
1496 ms125024 KiB
#include<bits/stdc++.h> #define int long long #define pb push_back #define fi first #define se second using namespace std; using ll = long long; using ld = long double; using ull = unsigned long long; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int maxN = 1e6 + 5; const int mod = 1e9 + 7; const ll oo = 1e18; int n, m; int a[maxN]; int st[4 * maxN]; void update(int id, int l, int r, int pos, int val) { if(l > pos || r < pos) return; if(l == r && l == pos) { st[id] = max(st[id], val); return; } int mid = (l + r) / 2; update(id * 2, l, mid, pos, val); update(id * 2 + 1, mid + 1, r, pos, val); st[id] = max(st[id * 2], st[id * 2 + 1]); } int get(int id, int l, int r, int u, int v) { if(l > v || r < u) return 0; if(l >= u && r <= v) return st[id]; int mid = (l + r) / 2; return max(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v)); } struct TQuery { int l, k, id; }; vector<TQuery> q[maxN]; void ReadInput() { cin >> n >> m; for(int i=1; i<=n; i++) cin >> a[i]; for(int i=1; i<=m; i++) { int l, r, k; cin >> l >> r >> k; q[r].pb({l, k, i}); } } int res[maxN]; void Solve() { stack<int> s; for(int i=1; i<=n; i++) { while(!s.empty() && a[s.top()] <= a[i]) s.pop(); if(!s.empty()) update(1, 1, n, s.top(), a[s.top()] + a[i]); s.push(i); for(TQuery a : q[i]) { res[a.id] = get(1, 1, n, a.l, i) <= a.k; } } for(int i=1; i<=m; i++) cout << res[i] << '\n'; } int32_t main() { // freopen("x.inp", "r", stdin); ios_base::sync_with_stdio(false); cin.tie(nullptr); ReadInput(); 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...