Submission #538967

#TimeUsernameProblemLanguageResultExecution timeMemory
538967akhan42Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++17
0 / 100
1296 ms262144 KiB
//#pragma GCC optimize("O3,unroll-loops") //#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #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; struct Seg { vi mx, t; vector<vi> sl; Seg(vi& a) { mx.assign(4 * n, -INF); t.assign(4 * n, -INF); sl.resize(4 * n); build(a); } void build(vi& a, int v = 1, int tl = 0, int tr = n - 1) { if(tl == tr) { mx[v] = a[tl]; sl[v].pb(a[tl]); return; } int tm = (tl + tr) / 2; build(a, 2 * v, tl, tm); build(a, 2 * v + 1, tm + 1, tr); mx[v] = max(mx[2 * v], mx[2 * v + 1]); merge(all(sl[2 * v]), all(sl[2 * v + 1]), back_inserter(sl[v])); t[v] = max(t[2 * v], t[2 * v + 1]); int ind = lower_bound(all(sl[2 * v + 1]), mx[2 * v]) - sl[2 * v + 1].begin(); if(ind != 0) maxeq(t[v], mx[2 * v] + sl[2 * v + 1][ind - 1]); } pair<bool, int> query(int l, int r, int k, int lp, int rp, int v = 1, int tl = 0, int tr = n - 1) { if(l > r) return {true, -INF}; if(tl == l && r == tr) { int indl = lower_bound(all(sl[v]), lp) - sl[v].begin(); int indr = lower_bound(all(sl[v]), rp + 1) - sl[v].begin(); bool ans = t[v] <= k && indl == indr; return {ans, mx[v]}; } int tm = (tl + tr) / 2; auto q1 = query(l, min(r, tm), k, lp, rp, 2 * v, tl, tm); if(q1.S > rp) { rp = q1.S - 1; lp = k - q1.S + 1; } auto q2 = query(max(l, tm + 1), r, k, lp, rp, 2 * v + 1, tm + 1, tr); return {q1.F && q2.F, max(q1.S, q2.S)}; } }; 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, (k + 1) / 2, (k - 1) / 2); cout << ans.F << '\n'; } // forn(k, 15) { // auto ans = seg.query(0, n - 1, k, (k + 1) / 2, (k - 1) / 2); // cout << k << ' ' << ans.F << '\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...