fork(1) download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/l7dTFa
BOI 2020 C
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!