Submission #1040420

#TimeUsernameProblemLanguageResultExecution timeMemory
1040420Neco_arcHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++17
0 / 100
113 ms7612 KiB
#include <bits/stdc++.h> #ifdef LOCAL #include <bits/debug.hpp> #endif // LOCAL #define ll long long #define all(x) x.begin(), x.end() #define Neco "Hedgehog Daniyar and Algorithms" #define resp(x) sort(all(x)), x.resize(unique(all(x)) - x.begin()) #define getbit(x,i) ((x >> i)&1) #define _left id * 2, l, mid #define _right id * 2 + 1, mid + 1, r #define cntbit(x) __builtin_popcountll(x) #define fi(i, a, b) for(int i = a; i <= b; i++) #define fid(i, a, b) for(int i = a; i >= b; i--) #define maxn (int) 2e5 + 7 using namespace std; const ll mod = 1e9 + 7; //972663749 const ll base = 911382323; int n, q; struct QUERY { int l, r, k, id; bool operator<(const QUERY &other) const { return r < other.r; } } qr[maxn]; int a[maxn]; namespace TRAU { int calc(int l, int r) { int Max = -1e9, ans = 0; fi(i, l, r) { if(a[i] < Max) ans = max(ans, a[i] + Max); Max = max(Max, a[i]); } return ans; } void solve() { fi(i, 1, q) { int l = qr[i].l, r = qr[i].r, k = qr[i].k; cout << (calc(l, r) <= k) << '\n'; } } } namespace Subtrask2 { int f[maxn], stk[maxn]; int ans[maxn]; struct IT { int st[4 * maxn]; void update(int x, int val, int id = 1, int l = 0, int r = n) { if(l > x || r < x) return ; if(l == r) return st[id] = max(st[id], val), void(); int mid = (l + r) >> 1; update(x, val, _left), update(x, val, _right); st[id] = max(st[id * 2], st[id * 2 + 1]); } int get(int u, int v, int id = 1, int l = 1, int r = n) { if(l > v || r < u) return 0; if(u <= l && r <= v) return st[id]; int mid = (l + r) >> 1; return max(get(u, v, _left), get(u, v, _right)); } } St; void prepare() { int top = 0; fi(i, 1, n) { while(top && a[i] >= a[stk[top]]) --top; f[i] = stk[top], stk[++top] = i; } } void solve() { prepare(); sort(qr + 1, qr + 1 + q); int j = 1; fi(i, 1, q) { while(j <= qr[i].r) { St.update(f[j], a[f[j]] + a[j]); ++j; } ans[qr[i].id] = (St.get(qr[i].l, qr[i].r) <= qr[i].k); } fi(i, 1, q) cout << ans[i] << '\n'; } } void solve() { cin >> n >> q; fi(i, 1, n) cin >> a[i]; fi(i, 1, q) cin >> qr[i].l >> qr[i].r >> qr[i].k, qr[i].id = i; Subtrask2::solve(); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if(fopen(Neco".inp", "r")) { freopen(Neco".inp", "r", stdin); freopen(Neco".out", "w", stdout); } int nTest = 1; // cin >> nTest; while(nTest--) { solve(); } return 0; }

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:125:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |         freopen(Neco".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:126:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |         freopen(Neco".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#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...