Submission #337758

#TimeUsernameProblemLanguageResultExecution timeMemory
337758BeanZHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++14
100 / 100
1948 ms125124 KiB
// I_Love_LPL #include <bits/stdc++.h> using namespace std; #define ll long long #define endl '\n' const int N = 1e6 + 50; long long mod = 1e9 + 7; const int lim = 700; const int lg = 18; const int base = 311; const long double eps = 1e-6; struct viet{ ll l, k, id; }; ll st[N * 4], a[N], ans[N]; void upd(ll k, ll l, ll r, ll x, ll v){ if (x > r || x < l) return; if (l == r){ st[k] = max(st[k], v); return; } ll mid = (l + r) >> 1; upd(k << 1, l, mid, x, v); upd(k << 1 | 1, mid + 1, r, x, v); st[k] = max(st[k << 1], st[k << 1 | 1]); } ll get(ll k, ll l, ll r, ll x, ll y){ if (x > r || y < l) return 0; if (x <= l && y >= r) return st[k]; ll mid = (l + r) >> 1; return max(get(k << 1, l, mid, x, y), get(k << 1 | 1, mid + 1, r, x, y)); } vector<viet> Q[N]; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); if (fopen("tests.inp", "r")){ freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout); } ll n, m; cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= m; i++){ ll l, r, k; cin >> l >> r >> k; Q[r].push_back({l, k, i}); } vector<ll> st; for (int i = 1; i <= n; i++){ while (st.size()){ if (a[st.back()] <= a[i]){ st.pop_back(); } else break; } if (st.size()) upd(1, 1, n, st.back(), a[st.back()] + a[i]); st.push_back(i); for (auto j : Q[i]){ ll val = get(1, 1, n, j.l, i); if (val > j.k) ans[j.id] = 0; else ans[j.id] = 1; } } for (int i = 1; i <= m; i++) cout << ans[i] << endl; } /* Ans: Out: */

Compilation message (stderr)

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