Submission #1107932

#TimeUsernameProblemLanguageResultExecution timeMemory
1107932LilPlutonHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++14
64 / 100
693 ms70308 KiB
#include <bits/stdc++.h> /// author: LilPluton auuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu using namespace std; #define int long long #define ld long double #define ar array #define pb push_back #define vi vector<int> #define vpi vector<pair<int,int>> #define pii pair<int,int> #define all(c) (c).begin(), (c).end() #define endll '\n' #define fastio ios::sync_with_stdio(0);cin.tie(0); #define lb(a, x) lower_bound(all(a), x) - a.begin(); #define ub(a, x) upper_bound(all(a), x) - a.begin(); template<typename T> bool umax(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; } template<typename T> bool umin(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; } mt19937 rng(time(0)); const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1}; const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1}; const int N = 2e5 + 5; int n, q; int a[N], mx[N << 2]; vi st[N << 2]; void build(int node,int l,int r){ mx[node] = 0; if(l == r){ st[node].pb(a[l]); return; } int mid = (l + r) >> 1; build(node * 2, l, mid); build(node * 2 + 1, mid + 1, r); st[node].resize(st[node * 2].size() + st[node * 2 + 1].size()); merge(all(st[node * 2]), all(st[node * 2 + 1]), begin(st[node])); if(st[node * 2].back() > st[node * 2 + 1][0]){ mx[node] = st[node * 2].back() + *--lower_bound(st[node * 2 + 1].begin(), st[node * 2 + 1].end(), st[node * 2].back()); } mx[node] = max({mx[node], mx[node * 2], mx[node * 2 + 1]}); } vi res; void get(int node,int l,int r,int lx,int rx){ if(l > rx || r < lx){ return; } if(l >= lx && r <= rx){ res.pb(node); return; } int mid = (l + r) >> 1; get(node * 2, l, mid, lx, rx); get(node * 2 + 1, mid + 1, r, lx, rx); } signed main() { fastio cin >> n >> q; for(int i = 1; i <= n; ++i){ cin >> a[i]; } build(1, 1, n); while(q--){ res.clear(); int l, r, x; cin >> l >> r >> x; get(1, 1, n, l, r); int curmx = 0, ans = 0; for(int &i : res){ umax(ans, mx[i]); } for(int i = 0; i < res.size() - 1; ++i){ int l = res[i], r = res[i + 1]; umax(curmx, st[l].back()); if(curmx > st[r][0]){ umax(ans, curmx + *--lower_bound(all(st[r]), curmx)); } } cout << (ans <= x) << endl; } }

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:74:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         for(int i = 0; i < res.size() - 1; ++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...