Submission #954090

#	Time	Username	Problem	Language	Result	Execution time	Memory
954090		Beerus13	Index (COCI21_index)	C++14	110 / 110	239 ms	37536 KiB

index

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
 
int n, q, a[N], ans[N];
int bit[N];
 
struct query {
    int l, r, id;
}; 
 
vector<int> pos[N];
vector<query> queries;
 
void update(int i, int val) {
    for(; i < N; i += i & -i) bit[i] += val;
}
 
int get(int i) {
    int res = 0;
    for(; i; i -= i & -i) res += bit[i];
    return res;
}
 
int Sum(int l, int r) {
    return get(r) - get(l - 1);
}
 
void solve(int l, int r, vector<query> &queries) {
    if(queries.empty()) return;
    if(l == r) {
        for(auto it : queries) ans[it.id] = l;
        return;
    }
    vector<query> L, R;
    int mid = l + r >> 1;
    for(int i = mid + 1; i <= r; ++i) {
        for(int j : pos[i]) update(j, 1);
    }
    for(auto it : queries) {
        if(Sum(it.l, it.r) > mid) R.push_back(it);
        else L.push_back(it);
    }
    solve(l, mid, L);
    for(int i = mid + 1; i <= r; ++i) {
        for(int j : pos[i]) update(j, -1);
    }
    solve(mid + 1, r, R);
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> q;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
        pos[a[i]].push_back(i);
    }
    for(int i = 1; i <= q; ++i) {
        int l, r; cin >> l >> r;
        queries.push_back({l, r, i});
    }
    solve(1, (int)2e5, queries);
    for(int i = 1; i <= q; ++i) cout << ans[i] << '\n';
    return 0;
}
 
// https://oj.vnoi.info/problem/coci2021_r6_index

Compilation message (stderr)

index.cpp: In function 'void solve(int, int, std::vector<query>&)':
index.cpp:36:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |     int mid = l + r >> 1;
      |               ~~^~~

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50