Submission #65505662

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Fenwick {
    int n;
    vector<int> bit;
    Fenwick(int _n): n(_n), bit(n+1, 0) {}
    void update(int i, int v){
        for(; i <= n; i += i & -i)
            bit[i] += v;
    }
    int query(int i) const {
        int s = 0;
        for(; i > 0; i -= i & -i)
            s += bit[i];
        return s;
    }
    int at(int i) const {
        return query(i) - query(i-1);
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Fenwick {
    int n;
    vector<int> bit;
    Fenwick(int _n): n(_n), bit(n+1, 0) {}
    void update(int i, int v){
        for(; i <= n; i += i & -i)
            bit[i] += v;
    }
    int query(int i) const {
        int s = 0;
        for(; i > 0; i -= i & -i)
            s += bit[i];
        return s;
    }
    int at(int i) const {
        return query(i) - query(i-1);
    }
    int find_by_order(int k) const {
        int idx = 0;
        int mask = 1 << 22;
        for(; mask > 0; mask >>= 1) {
            int next = idx + mask;
            if(next <= n && bit[next] < k) {
                idx = next;
                k -= bit[next];
            }
        }
        return idx + 1;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    const int M = 3000000;
    Fenwick fw(M);
    vector<bool> seen(M+1, false);
    for(int i = 1; i <= M; i++){
        fw.update(i, 1);
    }
    int Q;
    cin >> Q;
    while(Q--){
        int A, B;
        cin >> A >> B;
        if(A <= M && !seen[A]){
            seen[A] = true;
            for(int x = A; x <= M; x += A){
                if(fw.at(x) > 0)
                    fw.update(x, -1);
            }
        }
        int ans = fw.find_by_order(B);
        cout << ans << "\n";
    }
    return 0;
}

Submission Info

Judge Result