Submission #1110735

#TimeUsernameProblemLanguageResultExecution timeMemory
1110735luvnaIndex (COCI21_index)C++14
110 / 110
425 ms23252 KiB
#include<bits/stdc++.h> #define all(v) v.begin(), v.end() #define endl "\n" using namespace std; const int N = 2e5 + 15; int n, q; int a[N]; int L[N], R[N]; vector<int> candidate[N]; vector<int> evt; int bit[N]; pair<int,int> qu[N]; int ans[N]; void update(int idx, int v){ for(;idx <= n; idx += (idx & (-idx))) bit[idx] += v; } int get(int l, int r){int res = 0; l--; for(;r; r -= (r & (-r))) res += bit[r]; for(;l; l -= (l & (-l))) res -= bit[l]; return res; } void solve(){ cin >> n >> q; for(int i = 1; i <= n; i++) cin >> a[i], evt.push_back(i); sort(all(evt), [&](int x, int y){ return a[x] > a[y]; }); for(int i = 1; i <= q; i++){ int l, r; cin >> l >> r; qu[i] = {l,r}; L[i] = 1, R[i] = r - l + 1; } while(true){ bool any = false; for(int i = 1; i <= q; i++){ if(L[i] > R[i]) continue; int mid = (L[i] + R[i]) >> 1; candidate[mid].push_back(i); any = true; } if(!any) break; for(int mid = n, j = 0; mid >= 1; mid--){ while(j < evt.size() && a[evt[j]] >= mid){ update(evt[j],1); j++; } for(int i : candidate[mid]){ if(get(qu[i].first,qu[i].second) >= mid){ ans[i] = mid; L[i] = mid+1; } else R[i] = mid-1; } candidate[mid].clear(); } for(int i = 1; i <= n; i++) bit[i] = 0; } for(int i = 1; i <= q; i++) cout << ans[i] << endl; } signed main(){ ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0); #define task "task" if(fopen(task".INP", "r")){ freopen(task".INP", "r", stdin); freopen(task".OUT", "w", stdout); } int t; t = 1; //cin >> t; while(t--) solve(); }

Compilation message (stderr)

index.cpp: In function 'void solve()':
index.cpp:54:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |             while(j < evt.size() && a[evt[j]] >= mid){
      |                   ~~^~~~~~~~~~~~
index.cpp: In function 'int main()':
index.cpp:80:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         freopen(task".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
index.cpp:81:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         freopen(task".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...