#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define vi vector<ll>
#define vvi vector<vi>
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define ld long double
#define pii pair<ll, ll>
#define mt make_tuple
#define mn(a, b) a = min(a, b)
#define mx(a, b) a = max(a, b)
using namespace std;
const ll INF = (ll)2e9;
const ll inf = (ll)2e18;
const ld eps = (ld)1e-10;
const ll mod = (ll)1e9 + 7;
const ll MAXN = (ll)1e5 + 1;
const ll MAXC = (ll)2001;
const ll MAXE = (ll)1000;
const ll MAXLOG = 21;
const ll maxlen = (ll)1e5;
const ll asci = (ll)256;
const ll block = 50000;
const ld PI = acos(-1);
//
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<
ll,
null_type,
less<ll>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;*/
template <class T>
istream& operator >>(istream &in, vector<T> &arr){
for (T &cnt : arr) {
in >> cnt;
}
return in;
};
struct dsu{
int p[MAXN], sz[MAXN];
void clear(int n) {
for (int i = 0; i <= n; ++i) {
p[i] = i; sz[i] = 1;
}
}
int par(int v) {
if (p[v] == v) return v;
return p[v] = par(p[v]);
}
void unite(int v, int u) {
v = par(v), u = par(u);
if (v == u) return;
if (sz[v] < sz[u]) swap(v, u);
sz[v] += sz[u];
p[u] = v;
}
bool in(int v, int u) {
v = par(v), u = par(u);
if (v == u) return true;
return false;
}
};
dsu snm;
void solve() {
int n, m, q; cin >> n >> m >> q;
vi L(q, -1), R(q, m - 1), ok(q);
vector<pii> mid(q), check(q);
for (int i = 0; i < q; ++i) {
int v, u; cin >> v >> u;
check[i] = mp(v, u);
}
for (int i = 0; i < q; ++i) {
if (L[i] + 1 == R[i]) mid[i] = mp(-1, -1);
mid[i] = mp((L[i] + R[i]) / 2, i);
}
while (mid != vector<pii>(q, mp(-1, -1))) {
sort(all(mid)); snm.clear(n);
ok.assign(q, -1);
int it = 0;
for (int i = m; i >= 1; --i) {
for (int j = i; j + i <= n; j += i) {
snm.unite(j, j + i);
}
while (it < q && m - i >= mid[it].first) {
if (mid[it].first != -1) ok[mid[it].second] = snm.in(check[mid[it].second].first, check[mid[it].second].second);
it++;
}
}
for (int i = 0; i < q; ++i) {
if (ok[i] == -1) continue;
if (ok[i]) R[i] = (L[i] + R[i]) / 2;
else L[i] = (L[i] + R[i]) / 2;
}
for (int i = 0; i < q; ++i) {
if (L[i] + 1 == R[i]) mid[i] = mp(-1, -1);
else mid[i] = mp((L[i] + R[i]) / 2, i);
}
}
for (int i = 0; i < q; ++i) {
cout << R[i] + 1 << "\n";
}
}
int main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#endif
cout.precision(30);
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
760 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
1748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
84 ms |
5460 KB |
Output is correct |
| 2 |
Correct |
75 ms |
6168 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
127 ms |
7896 KB |
Output is correct |
| 2 |
Correct |
104 ms |
7796 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
108 ms |
3904 KB |
Output is correct |
| 2 |
Correct |
111 ms |
4420 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
128 ms |
4288 KB |
Output is correct |
| 2 |
Correct |
96 ms |
4960 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
190 ms |
5992 KB |
Output is correct |
| 2 |
Correct |
136 ms |
4784 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
118 ms |
7216 KB |
Output is correct |
| 2 |
Correct |
243 ms |
8072 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
274 ms |
7812 KB |
Output is correct |
| 2 |
Correct |
283 ms |
8964 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
344 ms |
8792 KB |
Output is correct |
| 2 |
Correct |
314 ms |
9960 KB |
Output is correct |
