Submission #898127

#TimeUsernameProblemLanguageResultExecution timeMemory
898127LitusianoHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++17
30 / 100
1408 ms207064 KiB
#pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #include<bits/stdc++.h> using namespace std; #define endl '\n' struct MST{ int n; vector<vector<int>> seg; void init(int n1){ n = 1; while(n < n1) n*=2; seg.assign(2*n, vector<int>()); } void merge(int i, int j, int k){ int l = 0; int r = 0; while(l < seg[j].size() && r < seg[k].size()){ if(seg[j][l] < seg[k][r]){ seg[i].push_back(seg[j][l]); l++; } else{ seg[i].push_back(seg[k][r]); r++; } } while(l < seg[j].size()){ seg[i].push_back(seg[j][l]); l++; } while(r < seg[k].size()){ seg[i].push_back(seg[k][r]); r++; } } void build(vector<int> v){ for(int i = n; i < 2*n; i++){ if(i-n >= v.size()) seg[i].push_back(0); else seg[i].push_back(v[i-n]); } for(int i = n-1; i>=0; i--){ merge(i,2*i, 2*i+1); } } int query(int ql, int qr, int v, int k, int l, int r){ if(r < ql || l > qr) return 0; if(ql <= l && r<= qr){ auto it = lower_bound(seg[k].begin(),seg[k].end(), v); if(it == seg[k].begin()) return 0; return *(it-1); } int m = (l+r) / 2; int x = query(ql, qr, v, 2*k, l ,m); int y = query(ql, qr, v, 2*k+1, m+1 ,r); return max(x,y); } int query(int ql, int qr, int v){ return query(ql, qr, v, 1, 0, n-1); } }; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n,q; cin>>n>>q; vector<int> v(n); for(int& i : v) cin>>i; vector<int> pre(n+1); vector<int> inv; for(int i = 1; i<n; i++){ pre[i+1] = pre[i] + (v[i] < v[i-1]); if(v[i] < v[i-1]) inv.push_back(i-1); } MST seg; seg.init(n); seg.build(v); while(q--){ int l,r,k; cin>>l>>r>>k; if(n > 5000){ if(pre[r] - pre[l] == 0) cout<<1<<endl; else cout<<0<<endl; } else{ l--; r--; int mx = 0; int idx = lower_bound(inv.begin(),inv.end(),l) - inv.begin(); // cerr<<"INV "; for(int x = idx; x < inv.size(); x++){ // cerr<<inv[x]<<" "; if(inv[x] >= r) break; int i = inv[x]; // cerr<<i+1<<" "<<r<<endl; // cerr<<"QUERY: "<<i<<" "<< seg.query(i+1,r,v[i])<<endl; int y = seg.query(i+1,r,v[i]); if(!y) continue; mx = max(mx, v[i] + y); } // cerr<<endl; if(mx > k) cout<<0<<endl; else cout<<1<<endl; } } }

Compilation message (stderr)

sortbooks.cpp: In member function 'void MST::merge(int, int, int)':
sortbooks.cpp:20:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |   while(l < seg[j].size() && r < seg[k].size()){
      |         ~~^~~~~~~~~~~~~~~
sortbooks.cpp:20:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |   while(l < seg[j].size() && r < seg[k].size()){
      |                              ~~^~~~~~~~~~~~~~~
sortbooks.cpp:28:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   while(l < seg[j].size()){
      |         ~~^~~~~~~~~~~~~~~
sortbooks.cpp:31:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   while(r < seg[k].size()){
      |         ~~^~~~~~~~~~~~~~~
sortbooks.cpp: In member function 'void MST::build(std::vector<int>)':
sortbooks.cpp:38:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |    if(i-n >= v.size()) seg[i].push_back(0);
      |       ~~~~^~~~~~~~~~~
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:87:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for(int x = idx; x < inv.size(); x++){
      |                      ~~^~~~~~~~~~~~
#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...