Submission #65507251

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;


#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef double db;

const int N = 4e6;

struct Fenwick
{
	int n;
	VL t;
	
	Fenwick(int _n = 0): n(_n), t(n) {}
	
	void upd(int i, LL x)
	{
		for (; i < n; i |= i + 1)
			t[i] += x;
	}
	LL query(int i)
	{
		LL ans = 0;
		for (; i >= 0; i = (i & (i + 1)) - 1)
			ans += t[i];
		return ans;
	}
	int lowerBound(LL x)
	{
		LL sum = 0;
		int i = -1;
		int lg = 31 - __builtin_clz(n);
		while (lg >= 0)
		{
			int j = i + (1 << lg);
			if (j < n && sum + t[j] < x)
			{
				sum += t[j];
				i = j;
			}
			lg--;
		}
		return i + 1;
	}

};

int val[N];


int main()
{
	ios::sync_with_stdio(0); 
	cin.tie(0);
	
	Fenwick fn(N);
	FOR (i, 1, N)
	{
		val[i] = 1;
		fn.upd(i, 1);
	}
		
	int q;
	cin >> q;
	set<int> used;
	FOR (i, 0, q)
	{
		int a, b;
		cin >> a >> b;
		if (!used.count(a))
			for (int j = a; j < N; j += a)
			{
				if (val[j])
				{
					fn.upd(j, -1);
					val[j] = 0;
				}
			}
		used.insert(a);
		cout << fn.lowerBound(b) << '\n';		
	}
		
	
	cerr << db(clock()) / CLOCKS_PER_SEC << '\n';
	
	return 0;
}

Submission Info

Judge Result