fork(1) download
  1. #define NDEBUG
  2.  
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. typedef long long ll;
  7. typedef long double ld;
  8. typedef double db;
  9. typedef string str;
  10.  
  11. typedef pair<int,int> pi;
  12. typedef pair<ll,ll> pl;
  13. typedef pair<db,db> pd;
  14.  
  15. typedef vector<int> vi;
  16. typedef vector<ll> vl;
  17. typedef vector<db> vd;
  18. typedef vector<str> vs;
  19. typedef vector<pi> vpi;
  20. typedef vector<pl> vpl;
  21. typedef vector<pd> vpd;
  22.  
  23. #define mp make_pair
  24. #define f first
  25. #define s second
  26. #define sz(x) (int)(x).size()
  27. #define all(x) begin(x), end(x)
  28. #define rall(x) (x).rbegin(), (x).rend()
  29. #define rsz resize
  30. #define ins insert
  31. #define ft front()
  32. #define bk back()
  33. #define pf push_front
  34. #define pb push_back
  35. #define eb emplace_back
  36. #define lb lower_bound
  37. #define ub upper_bound
  38.  
  39. #define FOR(i,a,b) for (int i = (a); i < (b); ++i)
  40. #define F0R(i,a) FOR(i,0,a)
  41. #define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
  42. #define R0F(i,a) ROF(i,0,a)
  43. #define trav(a,x) for (auto& a: x)
  44.  
  45. const int MOD = 1e9+7; // 998244353;
  46. const int MX = 2e5+5;
  47. const ll INF = 1e18;
  48. const ld PI = acos((ld)-1);
  49. const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1};
  50. mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
  51.  
  52. template<class T> bool ckmin(T& a, const T& b) {
  53. return b < a ? a = b, 1 : 0; }
  54. template<class T> bool ckmax(T& a, const T& b) {
  55. return a < b ? a = b, 1 : 0; }
  56. constexpr int pct(int x) { return __builtin_popcount(x); }
  57. constexpr int bits(int x) { return 31-__builtin_clz(x); } // floor(log2(x))
  58. ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
  59. ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down
  60. ll half(ll x) { return fdiv(x,2); }
  61.  
  62. template<class T, class U> T fstTrue(T lo, T hi, U f) {
  63. hi ++; assert(lo <= hi); // assuming f is increasing
  64. while (lo < hi) { // find first index such that f is true
  65. T mid = half(lo+hi);
  66. f(mid) ? hi = mid : lo = mid+1;
  67. }
  68. return lo;
  69. }
  70. template<class T, class U> T lstTrue(T lo, T hi, U f) {
  71. lo --; assert(lo <= hi); // assuming f is decreasing
  72. while (lo < hi) { // find first index such that f is true
  73. T mid = half(lo+hi+1);
  74. f(mid) ? lo = mid : hi = mid-1;
  75. }
  76. return lo;
  77. }
  78. template<class T> void remDup(vector<T>& v) {
  79. sort(all(v)); v.erase(unique(all(v)),end(v)); }
  80.  
  81. // INPUT
  82. template<class A> void re(complex<A>& c);
  83. template<class A, class B> void re(pair<A,B>& p);
  84. template<class A> void re(vector<A>& v);
  85. template<class A, size_t SZ> void re(array<A,SZ>& a);
  86.  
  87. template<class T> void re(T& x) { cin >> x; }
  88. void re(db& d) { str t; re(t); d = stod(t); }
  89. void re(ld& d) { str t; re(t); d = stold(t); }
  90. template<class H, class... T> void re(H& h, T&... t) { re(h); re(t...); }
  91.  
  92. template<class A> void re(complex<A>& c) { A a,b; re(a,b); c = {a,b}; }
  93. template<class A, class B> void re(pair<A,B>& p) { re(p.f,p.s); }
  94. template<class A> void re(vector<A>& x) { trav(a,x) re(a); }
  95. template<class A, size_t SZ> void re(array<A,SZ>& x) { trav(a,x) re(a); }
  96.  
  97. // TO_STRING
  98. #define ts to_string
  99. str ts(char c) { return str(1,c); }
  100. str ts(const char* s) { return (str)s; }
  101. str ts(str s) { return s; }
  102. str ts(bool b) {
  103. #ifdef LOCAL
  104. return b ? "true" : "false";
  105. #else
  106. return ts((int)b);
  107. #endif
  108. }
  109. template<class A> str ts(complex<A> c) {
  110. stringstream ss; ss << c; return ss.str(); }
  111. str ts(vector<bool> v) {
  112. str res = "{"; F0R(i,sz(v)) res += char('0'+v[i]);
  113. res += "}"; return res; }
  114. template<size_t SZ> str ts(bitset<SZ> b) {
  115. str res = ""; F0R(i,SZ) res += char('0'+b[i]);
  116. return res; }
  117. template<class A, class B> str ts(pair<A,B> p);
  118. template<class T> str ts(T v) { // containers with begin(), end()
  119. #ifdef LOCAL
  120. bool fst = 1; str res = "{";
  121. for (const auto& x: v) {
  122. if (!fst) res += ", ";
  123. fst = 0; res += ts(x);
  124. }
  125. res += "}"; return res;
  126. #else
  127. bool fst = 1; str res = "";
  128. for (const auto& x: v) {
  129. if (!fst) res += " ";
  130. fst = 0; res += ts(x);
  131. }
  132. return res;
  133.  
  134. #endif
  135. }
  136. template<class A, class B> str ts(pair<A,B> p) {
  137. #ifdef LOCAL
  138. return "("+ts(p.f)+", "+ts(p.s)+")";
  139. #else
  140. return ts(p.f)+" "+ts(p.s);
  141. #endif
  142. }
  143.  
  144. // OUTPUT
  145. template<class A> void pr(A x) { cout << ts(x); }
  146. template<class H, class... T> void pr(const H& h, const T&... t) {
  147. pr(h); pr(t...); }
  148. void ps() { pr("\n"); } // print w/ spaces
  149. template<class H, class... T> void ps(const H& h, const T&... t) {
  150. pr(h); if (sizeof...(t)) pr(" "); ps(t...); }
  151.  
  152. // DEBUG
  153. void DBG() { cerr << "]" << endl; }
  154. template<class H, class... T> void DBG(H h, T... t) {
  155. cerr << ts(h); if (sizeof...(t)) cerr << ", ";
  156. DBG(t...); }
  157. #ifdef LOCAL // compile with -DLOCAL
  158. #define dbg(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
  159. #else
  160. #define dbg(...) 0
  161. #endif
  162.  
  163. // FILE I/O
  164. void setIn(str s) { freopen(s.c_str(),"r",stdin); }
  165. void setOut(str s) { freopen(s.c_str(),"w",stdout); }
  166. void unsyncIO() { ios_base::sync_with_stdio(0); cin.tie(0); }
  167. void setIO(str s = "") {
  168. unsyncIO();
  169. // cin.exceptions(cin.failbit);
  170. // throws exception when do smth illegal
  171. // ex. try to read letter into int
  172. if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
  173. }
  174.  
  175. /**
  176.  * Description: Link-Cut Tree. Given a function $f(1\ldots N)\to 1\ldots N,$
  177.   * evaluates $f^b(a)$ for any $a,b.$ \texttt{sz} is for path queries;
  178.   * \texttt{sub}, \texttt{vsub} are for subtree queries. \texttt{x->access()}
  179.   * brings \texttt{x} to the top and propagates it; its left subtree will be
  180.   * the path from \texttt{x} to the root and its right subtree will be empty.
  181.   * Then \texttt{sub} will be the number of nodes in the connected component
  182.   * of \texttt{x} and \texttt{vsub} will be the number of nodes under \texttt{x}.
  183.   * Use \texttt{makeRoot} for arbitrary path queries.
  184.  * Time: O(\log N)
  185.  * Usage: FOR(i,1,N+1)LCT[i]=new snode(i); link(LCT[1],LCT[2],1);
  186.  * Source: Dhruv Rohatgi, Eric Zhang
  187. * https://sites.google.com/site/kc97ble/container/splay-tree/splaytree-cpp-3
  188. * https://c...content-available-to-author-only...s.com/blog/entry/67637
  189.  * Verification: (see README for links)
  190. * ekzhang Balanced Tokens
  191. * Dynamic Tree Test (Easy)
  192. * https://p...content-available-to-author-only...e.org/viewproblem.php?pid=578 (The Applicant)
  193.  */
  194.  
  195. typedef struct snode* sn;
  196. struct snode { //////// VARIABLES
  197. sn p, c[2]; // parent, children
  198. bool flip = 0; // subtree flipped or not
  199. int val, sz, mn; // value in node, # nodes in current splay tree
  200. snode(int _val) : val(_val) {
  201. p = c[0] = c[1] = NULL; calc(); }
  202. friend int getSz(sn x) { return x?x->sz:0; }
  203. friend int getMn(sn x) { return x?x->mn:MOD; }
  204. void prop() { // lazy prop
  205. if (!flip) return;
  206. swap(c[0],c[1]); flip = 0;
  207. F0R(i,2) if (c[i]) c[i]->flip ^= 1;
  208. }
  209. void calc() { // recalc vals
  210. mn = min(val,min(getMn(c[0]),getMn(c[1])));
  211. sz = 1+getSz(c[0])+getSz(c[1]);
  212. }
  213. //////// SPLAY TREE OPERATIONS
  214. int dir() {
  215. if (!p) return -2;
  216. F0R(i,2) if (p->c[i] == this) return i;
  217. return -1; // p is path-parent pointer
  218. } // -> not in current splay tree
  219. // test if root of current splay tree
  220. bool isRoot() { return dir() < 0; }
  221. friend void setLink(sn x, sn y, int d) {
  222. if (y) y->p = x;
  223. if (d >= 0) x->c[d] = y; }
  224. void rot() { // assume p and p->p propagated
  225. assert(!isRoot()); int x = dir(); sn pa = p;
  226. setLink(pa->p, this, pa->dir());
  227. setLink(pa, c[x^1], x); setLink(this, pa, x^1);
  228. pa->calc(); calc();
  229. }
  230. void splay() {
  231. while (!isRoot() && !p->isRoot()) {
  232. p->p->prop(), p->prop(), prop();
  233. dir() == p->dir() ? p->rot() : rot();
  234. rot();
  235. }
  236. if (!isRoot()) p->prop(), prop(), rot();
  237. prop();
  238. }
  239. //////// BASE OPERATIONS
  240. void access() { // bring this to top of tree, propagate
  241. for (sn v = this, pre = NULL; v; v = v->p) {
  242. v->splay(); // now switch virtual children
  243. v->c[1] = pre; v->calc(); pre = v;
  244. }
  245. splay(); assert(!c[1]); // right subtree is empty
  246. }
  247. void makeRoot() {
  248. access(); flip ^= 1; access(); assert(!c[0] && !c[1]); }
  249. //////// QUERIES
  250. friend sn lca(sn x, sn y) {
  251. if (x == y) return x;
  252. x->access(), y->access(); if (!x->p) return NULL;
  253. x->splay(); return x->p?:x; // y was below x in latter case
  254. } // access at y did not affect x -> not connected
  255. friend bool connected(sn x, sn y) { return lca(x,y); }
  256. // # nodes above
  257. int distRoot() { access(); return getSz(c[0]); }
  258. sn getRoot() { // get root of LCT component
  259. access(); sn a = this;
  260. while (a->c[0]) a = a->c[0], a->prop();
  261. a->access(); return a;
  262. }
  263. sn FBO() {
  264. prop();
  265. if (val == mn) return this;
  266. if (getMn(c[0]) == mn) return c[0]->FBO();
  267. assert(getMn(c[1]) == mn); return c[1]->FBO();
  268. }
  269. sn getMin() {
  270. access();
  271. return c[0]->FBO();
  272. }
  273. //////// MODIFICATIONS
  274. void set(int v) { access(); val = v; calc(); }
  275. friend void link(sn x, sn y, bool force = 0) {
  276. assert(x); assert(y);
  277. // dbg("LINK");
  278. assert(!connected(x,y));
  279. // dbg("OK");
  280. if (force) y->makeRoot(); // make x par of y
  281. else { y->access(); assert(!y->c[0]); }
  282. // dbg("OK");
  283. x->access(); setLink(y,x,0);
  284. // dbg("BEFORECALC");
  285. y->calc();
  286. // dbg("FIXEDLINK");
  287. }
  288. friend void cut(sn y) { // cut y from its parent
  289. y->access(); assert(y->c[0]);
  290. y->c[0]->p = NULL; y->c[0] = NULL; y->calc(); }
  291. friend void cut(sn x, sn y) { // if x, y adj in tree
  292. x->makeRoot(); y->access();
  293. assert(y->c[0] == x && !x->c[0] && !x->c[1]); cut(y); }
  294. };
  295. sn LCT[600005];
  296.  
  297. pi ed[400005];
  298. int N,M,Q, rig[400005];
  299. bool in[400005];
  300.  
  301. void del(int ind) {
  302. assert(in[ind]);
  303. cut(LCT[ed[ind].f],LCT[ind]);
  304. cut(LCT[ed[ind].s],LCT[ind]);
  305. in[ind] = 0;
  306. }
  307.  
  308. bool link(int ind) {
  309. in[ind] = 1;
  310. int u = ed[ind].f, v = ed[ind].s;
  311. assert(!connected(LCT[u],LCT[v]));
  312. link(LCT[u],LCT[ind],1);
  313. link(LCT[v],LCT[ind],1);
  314. return 1;
  315. }
  316.  
  317. bool ad(int ind) {
  318. int u = ed[ind].f, v = ed[ind].s;
  319. if (!connected(LCT[u],LCT[v])) return link(ind);
  320. LCT[u]->makeRoot();
  321. if (LCT[v]->distRoot()%4 == 0) return 0;
  322. sn s = LCT[v]->getMin(); assert(s->val != MOD);
  323. del(s->val); return link(ind);
  324. }
  325.  
  326. // oops did I really need this to pass
  327.  
  328. /**
  329.  * Description: Fast input and output.
  330.  * Time: input is $\sim$300ms faster for $10^6$ long longs on CF
  331.  * Source:
  332.   * https://c...content-available-to-author-only...s.com/gym/102394/submission/64154785
  333.   * https://c...content-available-to-author-only...s.com/contest/1254/submission/65420506 (neal)
  334.   * https://c...content-available-to-author-only...s.com/blog/entry/45835 (AI.Cash)
  335.  * Verification: https://c...content-available-to-author-only...s.com/gym/102394/problem/G
  336.  */
  337.  
  338. namespace FastIO {
  339. const int BSZ = 1<<15; ////// INPUT
  340. char ibuf[BSZ]; int ipos, ilen;
  341. char nc() { // next char
  342. if (ipos == ilen) {
  343. ipos = 0; ilen = fread(ibuf,1,BSZ,stdin);
  344. if (!ilen) return EOF;
  345. }
  346. return ibuf[ipos++];
  347. }
  348. void rs(str& x) { // read str
  349. char ch; while (isspace(ch = nc()));
  350. do { x += ch; } while (!isspace(ch = nc()) && ch != EOF);
  351. }
  352. template<class T> void ri(T& x) { // read int or ll
  353. char ch; int sgn = 1;
  354. while (!isdigit(ch = nc())) if (ch == '-') sgn *= -1;
  355. x = ch-'0'; while (isdigit(ch = nc())) x = x*10+(ch-'0');
  356. x *= sgn;
  357. }
  358. template<class T, class... Ts> void ri(T& t, Ts&... ts) {
  359. ri(t); ri(ts...); } // read ints
  360. ////// OUTPUT (call initO() at start)
  361. char obuf[BSZ], numBuf[100]; int opos;
  362. void flushOut() { fwrite(obuf,1,opos,stdout); opos = 0; }
  363. void wc(char c) { // write char
  364. if (opos == BSZ) flushOut();
  365. obuf[opos++] = c; }
  366. void ws(str s) { trav(c,s) wc(c); } // write str
  367. template<class T> void wi(T x, char after = '\0') { /// write int
  368. if (x < 0) wc('-'), x *= -1;
  369. int len = 0; for (;x>=10;x/=10) numBuf[len++] = '0'+(x%10);
  370. wc('0'+x); R0F(i,len) wc(numBuf[i]);
  371. if (after) wc(after);
  372. }
  373. void initO() { assert(atexit(flushOut) == 0); } /// auto-flush output
  374. }
  375. using namespace FastIO;
  376. /// initO(); int a,b; ri(a,b); wi(b,'\n'); wi(a,'\n');
  377.  
  378. int main() {
  379. initO();
  380. ri(N,M,Q);
  381. dbg(Q);
  382. FOR(i,1,N+1) {
  383. LCT[2*M+i] = new snode(MOD);
  384. //dbg("OK",M+i);
  385. }
  386. F0R(i,M) {
  387. ri(ed[i].f,ed[i].s);
  388. ed[i].f += 2*M, ed[i].s += 2*M;
  389. LCT[i] = new snode(i);
  390. dbg(ed[i]);
  391. }
  392. FOR(i,M,2*M) {
  393. ed[i] = ed[i-M];
  394. LCT[i] = new snode(i);
  395. }
  396. int r = -1;
  397. F0R(i,2*M) {
  398. while (r < 2*M-1 && ad(r+1)) r ++;
  399. rig[i] = r;
  400. if (in[i]) del(i);
  401. dbg(i,rig[i]);
  402. }
  403. F0R(i,Q) {
  404. int l,r; ri(l,r); l--,r--;
  405. if (rig[r+1] >= M+l-1) ws("NO\n");
  406. else ws("YES\n");
  407. }
  408. flushOut();
  409. // you should actually read the stuff at the bottom
  410. }
  411.  
  412. /* stuff you should look for
  413. * int overflow, array bounds
  414. * special cases (n=1?)
  415. * do smth instead of nothing and stay organized
  416. * WRITE STUFF DOWN
  417. */
  418.  
Time limit exceeded #stdin #stdout 5s 4540KB
stdin
Standard input is empty
stdout
Standard output is empty