oj.uz

Submission #925826

# Submission time Handle Problem Language Result Execution time Memory
925826 2024-02-12T09:32:59 Z vjudge1 Joker (BOI20_joker) C++17
0 / 100
 1725 ms 13460 KB 
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")

#include<bits/stdc++.h>	

using namespace std;

#define all(a) a.begin(), a.end()                                                   
#define rall(a) a.rbegin(), a.rend()                 
#define sz(a) (int)a.size()
#define s second
#define f first
 
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
     
vector<pii> rid = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
vector<pii> dir = {{-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
 
const int N = 4e5 + 1, mod = 998244353;

const ll inf = 1e9;
 
double eps = 1e-15;
                                                
bool flg = 0;

const int k = 300;

bool ok, was[N];
vector<pii> g(N);

int p[N + 1], sz[N + 1], pt[N + 1];
vector<array<int, 3>> h;

pii get(int x) {
 	if (p[x] == x) return {x, 0};
 	pii val = get(p[x]);
 	return {val.f, (1 + val.s) % 2};
}

void add(int id) {
	int u = g[id].f;
	int v = g[id].s;
	pii x = get(u);
	pii y = get(v);
	if (x.f == y.f) {
		if (x.s == y.s) {
			if (ok) {
			    h.push_back({-1, -1, -1});
				ok = 0;
			}    
		}
		return;
	}
	if (sz[x.f] > sz[y.f]) swap(x, y);
	h.push_back({x.f, p[x.f], sz[x.f]});
	h.push_back({y.f, p[y.f], sz[y.f]});
	p[x.f] = y.f;  	
	sz[y.f] += sz[x.f];
}

void rb() {
	while (sz(h) && !pt[sz(h)]) {
		array<int, 3> x = h.back();
		h.pop_back();
		if (x[0] == -1) {
			ok = 1;
			continue;
		}
		p[x[0]] = x[1];
		sz[x[0]] = x[2];
	}
	pt[sz(h)] = 0; 
}

bool slave(int l, int r) {
	for (int i = l; i <= r; i++) add(i);
	bool vv = ok;
	rb();
	return vv;	
}

bool cmp(array<int, 3> a, array<int, 3> b) {
	if (a[0] / k < b[0] / k) return 1;
	if (a[0] / k == b[0] / k && a[1] < b[1]) return 1;
	return 0;
}

void slv() {
	int n, m, q;
	cin >> n >> m >> q;
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		g[i] = g[i + m] = {u, v};
	}
	for (int i = 1; i <= n; i++) 
		p[i] = i, sz[i] = 1;
	vector<array<int, 3>> qr;
	bool ans[q + 1];
	ok = 1;
	for (int i = 1; i <= q; i++) {
		int l, r;
		cin >> l >> r;
		int tl = r + 1, tr = m + l - 1;
		if (tl / k == tr / k) 
			ans[i] = slave(tl, tr);
		else qr.push_back({tl, tr, i});
	}
	sort(all(qr), cmp);
	int tr = 0, lst = -1, pos;
	for (auto [l, r, id]: qr) {
		if (l / k != lst) {
			rb();
			lst = l / k;
			pos = (lst + 1) * k - 1;
			tr = pos;
		}
		while (tr < r) 
			add(++tr);
		pt[sz(h)] = 1;
		for (int i = pos; i >= l; i--) 
			add(i);
		ans[id] = ok;
		rb();
		
	}
	for (int i = 1; i <= q; i++) {
		if (ans[i]) cout << "NO\n";
		else cout << "YES\n";
	}
}                                                                           
 
main() {
	//freopen("rsq.in", "r", stdin);                                                                                     
	//freopen("rsq.out", "w", stdout);                                                                                     
	ios_base::sync_with_stdio(0);	                                                                                       
	cin.tie(0);
	int tp = 1;
	if (flg) cin >> tp;
	while (tp--) {  	
		slv();
	}
}
//wenomechainsama

Compilation message

Joker.cpp:138:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  138 | main() {
      | ^~~~
Joker.cpp: In function 'void slv()':
Joker.cpp:126:3: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
  126 |   for (int i = pos; i >= l; i--)
      |   ^~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7516 KB Output is correct
2 Correct 2 ms 7708 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Incorrect 2 ms 7516 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7516 KB Output is correct
2 Correct 2 ms 7708 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Incorrect 2 ms 7516 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7516 KB Output is correct
2 Correct 2 ms 7708 KB Output is correct
3 Incorrect 1725 ms 13460 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7516 KB Output is correct
2 Correct 2 ms 7708 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Incorrect 2 ms 7516 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7516 KB Output is correct
2 Correct 2 ms 7708 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Incorrect 2 ms 7516 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7516 KB Output is correct
2 Correct 2 ms 7708 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Incorrect 2 ms 7516 KB Output isn't correct
5 Halted 0 ms 0 KB -