Submission #154109

#TimeUsernameProblemLanguageResultExecution timeMemory
154109beso123Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++14
64 / 100
3020 ms84076 KiB
#include<bits/stdc++.h> using namespace std; const int N = 1e6+9; int w[N], l[N], n, m,ans[N], L[N], R[N], F[N]; set<int > s; void ad(int l, int r){ auto it = s.lower_bound(l); if(it != s.end() && F[*it] <= r) return; while(it != s.begin() && F[*(--it)] >= r){ s.erase(it); it = s.lower_bound(l); } F[l] =r; s.insert(l); } main(){ int n; cin >> n >> m; for(int i = 1; i <= n; i++){ scanf("%d",&w[i]); } stack<int> S; for(int i = 1; i <= n; i++){ while(S.size() && w[S.top()] <= w[i]) S.pop(); if(!S.size()) l[i] = 0; else l[i] = S.top(); S.push(i); } vector<pair<int, pair<int,int> > > v; for(int i = 1; i <= n; i++){ if(l[i]) v.push_back({-w[l[i]] - w[i], {l[i], i}}); } sort(v.begin(), v.end()); vector<pair<int,int> > Q; for(int i = 1; i <= m; i++){ int k; scanf("%d%d%d", &L[i],&R[i], &k); Q.push_back({-k, i}); } sort(Q.begin(), Q.end()); int j = 0; for(int i = 0; i < Q.size(); i++){ while(j < v.size() && v[j].first < Q[i].first){ ad(v[j].second.first, v[j].second.second); j++; } int I = Q[i].second; int l = L[I], r =R[I]; auto it = s.lower_bound(l); if(it == s.end() || F[*it] > r) ans[I] = 1; } for(int i = 1; i <= m; i++) printf("%d\n",ans[i]); }

Compilation message (stderr)

sortbooks.cpp:17:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:44:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < Q.size(); i++){
                    ~~^~~~~~~~~~
sortbooks.cpp:45:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(j < v.size() && v[j].first < Q[i].first){
               ~~^~~~~~~~~~
sortbooks.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&w[i]);
         ~~~~~^~~~~~~~~~~~
sortbooks.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &L[i],&R[i], &k);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...