Submission #1192835

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192835		nguyenkhangninh99	Index (COCI21_index)	C++20	110 / 110	562 ms	13216 KiB

index

#include <bits/stdc++.h>
using namespace std;
  
const int BLOCK_SIZE = 320;

struct FenwickTree{
    vector<int> tree;
 
    void init(int n){
        tree.assign(n + 2, 0);
        
    }
 
    void update(int v, int val) {
        for (; v < tree.size(); v += v & (-v)){
            tree[v]+= val;
        }
    }
    
    int get(int v) {
        int res = 0;
        for (; v; v -= v & (-v)){
            res += tree[v];
        }
        return res;
    }
} bit;

bool cmp(array<int, 3> a, array<int, 3> b) {
    if (a[0] / BLOCK_SIZE == b[0] / BLOCK_SIZE) return a[1] < b[1];
    return a[0] / BLOCK_SIZE < b[0] / BLOCK_SIZE;
}
 
void solve(){
    int n, q; cin >> n >> q;

    vector<int> p(n + 1), ans(q + 1);
    vector<array<int, 3>> qry(q + 1);

    for(int i = 1; i <= n; i++) cin >> p[i];

    for(int i = 1; i <= q; i++){
        int l, r; cin >> l >> r;
        qry[i] = {l, r, i};
    }

    sort(qry.begin() + 1, qry.end(), cmp);
    bit.init(2000005);

    int curl = 1, curr = 0;
	for(int i = 1; i <= q; i++) {
		int l = qry[i][0], r = qry[i][1];
		while(curl > l){
            curl--; 
            bit.update(p[curl], 1);
		}
		while(curl < l) {
			bit.update(p[curl], -1); 
            curl++;
		}
		while(curr < r){
			curr++;
			bit.update(p[curr], 1);		
		}
		while(curr > r) {
			bit.update(p[curr], -1); 
			curr--;
		} 

		int low = 1, high = 2000000, res = 1;
		while(low <= high) {
			int mid = (low + high) / 2;
			if(bit.get(2000000) - bit.get(mid - 1) >= mid){
				low = mid + 1;
				res = mid;
			} else high = mid - 1;
		}
		ans[qry[i][2]] = res;
	}

	for(int i = 1; i <= q; i++) cout << ans[i] << "\n";
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    solve();
    return 0;
}

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