Submission #954089

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
954089	2024-03-27T09:10:45 Z	Beerus13	Index (COCI21_index)	C++14	Compilation error	0 ms	0 KB

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 < ar; 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

index.cpp: In function 'void update(int, int)':
index.cpp:16:15: error: 'ar' was not declared in this scope; did you mean 'a'?
   16 |     for(; i < ar; i += i & -i) bit[i] += val;
      |               ^~
      |               a
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;
      |               ~~^~~