Submission #1058536

#TimeUsernameProblemLanguageResultExecution timeMemory
1058536_shr104Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++14
100 / 100
573 ms75484 KiB
#include <bits/stdc++.h> using namespace std; typedef int ll; typedef long double ld; #define pb push_back #define pf push_front #define fi first #define se second const ll mod = 1e9+7, mxn = 1e6+7; ll bit[mxn], n, q, w[mxn], lis[mxn]; bool ans[mxn]; vector<vector<pair<pair<ll,ll>,ll>>> qx(mxn); void upd(ll u, ll v) {while (u) {bit[u] = max(bit[u],v); u -= (u&(-u));}} ll get(ll u) {if (!u) {return 1e18;} ll sum = 0; while (u < mxn) {sum = max(sum,bit[u]); u += (u&(-u));} return sum;} signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("test.inp","r",stdin); freopen("test.out","w",stdout); freopen("test.err","w",stderr); cin >> n >> q; for (ll i = 1; i <= n; i++) { cin >> w[i]; lis[i] = i-1; while (lis[i] && w[i] >= w[lis[i]]) lis[i] = lis[lis[i]]; // cerr << lis[i] << ' '; } for (ll i = 1; i <= q; i++) { ll l, r, c; cin >> l >> r >> c; qx[r].pb({{l,i},c}); } for (ll i = 1; i <= n; i++) { upd(lis[i],w[lis[i]]+w[i]); for (pair<pair<ll,ll>,ll> j : qx[i]) ans[j.fi.se] = (get(j.fi.fi) <= j.se); } for (ll i = 1; i <= q; i++) cout << ans[i] << '\n'; }

Compilation message (stderr)

sortbooks.cpp: In function 'll get(ll)':
sortbooks.cpp:14:31: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
   14 | ll get(ll u) {if (!u) {return 1e18;} ll sum = 0; while (u < mxn) {sum = max(sum,bit[u]); u += (u&(-u));} return sum;}
      |                               ^~~~
#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...