#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
const int MOD = 1000000007;
const ll INF = 1e18;
// const int MX = 100001;
/**
* Description: more convenient functions for input / output
* experimentation with C++11 features
*/
namespace io {
template<typename Test, template<typename...> class Ref>
struct is_specialization : std::false_type {};
template<template<typename...> class Ref, typename... Args>
struct is_specialization<Ref<Args...>, Ref>: std::true_type {};
// https://stackoverflow.com/questions/16337610/how-to-know-if-a-type-is-a-specialization-of-stdvector
void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
void setIO(string s = "") {
ios_base::sync_with_stdio(0); cin.tie(0);
if (sz(s)) { setIn(s+".in"), setOut(s+".out"); }
}
// INPUT
// double input seems slow on CF
void re(double& x) { string t; cin >> t; x = stod(t); }
void re(ld& x) { string t; cin >> t; x = stold(t); }
template<class T> void re(T& x) { cin >> x; }
template<class Arg, class... Args> void re(Arg& first, Args&... rest) {
re(first); re(rest...);
}
template<class T1, class T2> istream& operator>>(istream& is, pair<T1,T2>& p) {
is >> p.f >> p.s; return is;
}
template<class T> istream& operator>>(istream& is, vector<T>& a) {
F0R(i,sz(a)) is >> a[i];
return is;
}
// OUTPUT
template<class T> void pr(const T& x) { cout << x << '\n'; }
template<class Arg, class... Args> void pr(const Arg& first, const Args&... rest) {
cout << first << ' '; pr(rest...);
}
template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) {
os << '{' << a.f << ", " << a.s << '}'; return os;
}
template<class T> ostream& operator<<(ostream& os, const vector<T>& a) {
os << '{';
F0R(i,sz(a)) {
if (i) {
os << ", ";
if (is_specialization<T, vector>::value) os << '\n';
}
os << a[i];
}
os << '}';
return os;
}
}
using namespace io;
template<int SZ> struct DSU {
int par[SZ], sz[SZ];
DSU() {
F0R(i,SZ) par[i] = i, sz[i] = 1;
}
int get(int x) { // path compression
if (par[x] != x) par[x] = get(par[x]);
return par[x];
}
bool unite(int x, int y) { // union-by-rank
x = get(x), y = get(y);
if (x == y) return 0;
if (sz[x] < sz[y]) swap(x,y);
sz[x] += sz[y], par[y] = x;
return 1;
}
};
template<int SZ> struct queryConnect {
int n,q; // vertices, edges, # queries
vpi ed; // edges
pi p[SZ]; // connectivity queries
int l[SZ],r[SZ]; // left and right bounds for answer
vi tri[SZ];
bool left() {
F0R(i,sz(ed)+1) tri[i].clear();
bool ok = 0;
F0R(i,q) if (l[i] != r[i]) {
tri[(l[i]+r[i])/2].pb(i);
ok = 1;
}
return ok;
}
void test() {
DSU<SZ> D = DSU<SZ>();
F0R(i,sz(ed)+1) {
if (i) D.unite(ed[i-1].f,ed[i-1].s);
for (int x: tri[i]) {
if (D.get(p[x].f) == D.get(p[x].s)) r[x] = i;
else l[x] = i+1;
}
}
}
void solve() {
F0R(i,q) l[i] = 0, r[i] = sz(ed)+1;
while (left()) test();
}
};
DSU<100001> D;
queryConnect<100001> Q;
int m;
int main() {
setIO();
re(Q.n,m,Q.q);
FOR(i,1,m+1) {
int t = m+1-i;
for (int j = t; j+t <= Q.n; j += t) if (D.unite(j,j+t)) Q.ed.pb({j,j+t});
}
// cout << sz(Q.ed) << "\n";
// exit(0);
F0R(i,Q.q) {
// re(Q.p[i]);
Q.p[i] = {rand() % 100000+1, rand() % 100000+1};
}
Q.solve();
F0R(i,Q.q) {
if (Q.l[i] == 0) {
cout << "0\n";
} else {
Q.l[i] --;
cout << m+1-__gcd(Q.ed[Q.l[i]].f,Q.ed[Q.l[i]].s) << "\n";
}
}
}
/*
* (Actually read this pls)
* Rlly bad errors: int overflow, array bounds
* Less bad errors: special cases (n=1?), set tle
* Common sense: do smth instead of nothing
*/
Compilation message
pictionary.cpp: In function 'void io::setIn(std::__cxx11::string)':
pictionary.cpp:61:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
void setIn(string s) { freopen(s.c_str(),"r",stdin); }
~~~~~~~^~~~~~~~~~~~~~~~~~~~~
pictionary.cpp: In function 'void io::setOut(std::__cxx11::string)':
pictionary.cpp:62:36: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
5368 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
6140 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
8668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
10040 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
10040 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
10040 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
72 ms |
11056 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
97 ms |
13496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
110 ms |
14068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
146 ms |
15796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
