Submission #923478

#TimeUsernameProblemLanguageResultExecution timeMemory
923478IsamIndex (COCI21_index)C++17
20 / 110
6 ms8284 KiB
#include<bits/stdc++.h> using namespace std; constexpr int sz = 1001; int n, Q, c[sz], ans[sz]; int j, tree[sz][sz]; inline void update(int pos, int val){ while(pos <= n){ tree[j][pos] += val; pos += (pos & (-pos)); } return; } int get_ans(int l, int r){ if(!r || l > r) return 0; if(l ^ 1) return get_ans(1, r) - get_ans(1, l - 1); int res(0); while(r > 0){ res += tree[j][r]; r -= (r & (-r)); } return res; } struct que{ int index, l, r; } q[sz]; bool cmp(que a, que b){ if(a.r ^ b.r) return a.r < b.r; return a.l < b.l; } bool check(int mid, int l, int r){ int cur(0); j = r; cur += get_ans(mid, n); j = l - 1; if(j > 0) cur -= get_ans(mid, n); return cur >= mid; } signed main(){ ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin >> n >> Q; for(register int i = 1; i <= n; ++i){ cin >> c[i]; for(j = i; j <= n; ++j){ update(c[i], 1); } } for(register int i = 1; i <= Q; ++i){ cin >> q[i].l >> q[i].r, q[i].index = i; } sort(q+1, q+Q+1, cmp); int i(1), l, r; while(i <= n){ l = q[i].l, r = q[i].r; int L(1), R(r - l + 1), mid, best(1); while(L <= R){ mid = L + ((R - L) >> 1); if(check(mid, l, r)){ best = mid; L = mid + 1; }else{ R = mid - 1; } } ans[q[i].index] = best; ++i; } for(register int i = 1; i <= Q; ++i){ cout << ans[i] << '\n'; } return 0; } /* 7 6 3 2 3 1 1 4 7 3 4 1 7 1 6 4 5 1 2 5 7 */

Compilation message (stderr)

index.cpp: In function 'int main()':
index.cpp:56:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   56 |  for(register int i = 1; i <= n; ++i){
      |                   ^
index.cpp:62:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   62 |  for(register int i = 1; i <= Q; ++i){
      |                   ^
index.cpp:91:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   91 |  for(register int i = 1; i <= Q; ++i){
      |                   ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...