Submission #1095113

#TimeUsernameProblemLanguageResultExecution timeMemory
1095113KasymKHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++17
100 / 100
1191 ms124752 KiB
#include "bits/stdc++.h" using namespace std; #define ff first #define ss second #define all(v) v.begin(), v.end() #define ll long long #define pb push_back #define pii pair<int, int> #define pli pair<ll, int> #define pll pair<ll, ll> #define tr(i, c) for(auto i = c.begin(); i != c.end(); ++i) #define wr puts("----------------") template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;} template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;} const int N = 1e6+6; const int INF = 2e9; int v[N], id[N], l[N], r[N], k[N], ans[N]; vector<int> Q[N]; struct node{ int l, r, val; } seg[N<<2]; void build(int x, int l, int r){ seg[x].l = l, seg[x].r = r; if(l == r){ seg[x].val = -INF; return; } int mid = (l+r)>>1; build(x<<1, l, mid); build(x<<1|1, mid+1, r); seg[x].val = max(seg[x<<1].val, seg[x<<1|1].val); } void update(int x, int k, int u){ if(seg[x].l == seg[x].r){ seg[x].val = u; return; } int mid = (seg[x].l+seg[x].r)>>1; if(k <= mid) update(x<<1, k, u); else update(x<<1|1, k, u); seg[x].val = max(seg[x<<1].val, seg[x<<1|1].val); } int query(int x, int l, int r){ if(seg[x].l == l and seg[x].r == r) return seg[x].val; int mid = (seg[x].l+seg[x].r)>>1; if(r <= mid) return query(x<<1, l, r); else if(l > mid) return query(x<<1|1, l, r); else return max(query(x<<1, l, mid), query(x<<1|1, mid+1, r)); } int main(){ // freopen("file.txt", "r", stdin); int n, q; scanf("%d%d", &n, &q); for(int i = 1; i <= n; ++i){ int x; scanf("%d", &x); v[i] = x; } stack<int> st; for(int i = 1; i <= n; ++i){ while(!st.empty() and v[st.top()] <= v[i]) st.pop(); if(st.empty()) id[i] = -1; else id[i] = st.top(); st.push(i); } // for(int i = 1; i <= n; ++i) // printf("%d ", id[i]); // puts(""); // wr; for(int i = 1; i <= q; ++i){ scanf("%d%d%d", &l[i], &r[i], &k[i]); Q[r[i]].pb(i); } build(1, 1, n); for(int j = 1; j <= n; ++j){ int i = id[j]; if(~i) update(1, i, v[i]+v[j]); for(auto &ww : Q[j]) ans[ww] = (query(1, l[ww], r[ww]) <= k[ww]); } for(int i = 1; i <= q; ++i) printf("%d\n", ans[i]); return 0; }

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |     scanf("%d%d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~
sortbooks.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         scanf("%d", &x);
      |         ~~~~~^~~~~~~~~~
sortbooks.cpp:85:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |         scanf("%d%d%d", &l[i], &r[i], &k[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...