oj.uz

Submission #1026010

# Submission time Handle Problem Language Result Execution time Memory
1026010 2024-07-17T12:31:49 Z Tob Long Mansion (JOI17_long_mansion) C++14
100 / 100
 631 ms 150244 KB 
#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll val(ll x) {
	uniform_int_distribution <ll> rnd(0, x-1);
	return rnd(rng);
}

const int N = 5e5 + 7, ofs = (1 << 19), inf = 1e9;

int n, q;
int c[N], res[N], lli[N], rli[N];
vector <int> d[N], g[N], h[N];
vector <pii> qu1[N], qu2[N];

int t[2*ofs];
struct Tr {
	int type, non;
	int Merge(int x, int y) {return type ? min(x, y) : max(x, y);}
	int Good(int x, int y) {return type ? (x <= y) : (x >= y);}
	void init(int ty, int ne, vector <int>& v) {
		type = ty; non = ne;
		for (int i = ofs; i < 2*ofs; i++) t[i] = non;
		for (int i = 0; i < v.size(); i++) t[i+ofs] = v[i];
		for (int i = ofs-1; i; i--) t[i] = Merge(t[2*i], t[2*i+1]);
		v.clear();
	}
	int query(int x, int a, int b, int lo = 0, int hi = ofs-1) {
		if (b < lo || hi < a) return non;
		if (a <= lo && hi <= b) return t[x];
		int mid = (lo + hi) / 2;
		return Merge(query(2*x, a, b, lo, mid), query(2*x+1, a, b, mid+1, hi));
	}
	int get(int x, int a, int b, int val, int lo = 0, int hi = ofs-1) {
		if (b < lo || hi < a) return -1;
		if (a <= lo && hi <= b && !Good(t[x], val)) return -1;
		if (lo == hi) return x-ofs;
		int mid = (lo + hi) / 2, mi = (hi-lo+1)/2*type;
		int lc = get(2*x+type, a, b, val, lo+mi, mid+mi);
		if (lc == -1) return get(2*x+1-type, a, b, val, mid+1-mi, hi-mi);
		return lc;
	}
} T;

int main () {
	FIO;
	cin >> n;
	for (int i = 0; i < n; i++) g[i].pb(-1);
	for (int i = 0; i < n-1; i++) {
		cin >> c[i]; c[i]--;
		g[c[i]].pb(i);
	}
	for (int i = 0; i < n; i++) g[i].pb(n-1);
	for (int i = 0; i < n; i++) h[i].pb(-1);
	for (int i = 0; i < n; i++) {
		int b; cin >> b;
		for (int j = 0; j < b; j++) {
			int x; cin >> x; x--;
			d[i].pb(x);
			h[x].pb(i);
		}
	}
	for (int i = 0; i < n; i++) h[i].pb(n);
	
	cin >> q;
	for (int i = 0; i < q; i++) {
		int x, y; cin >> x >> y; x--; y--;
		if (x > y) qu1[x].pb({y, i});
		else qu2[x].pb({y, i});
	}
	for (int i = 0; i < n-1; i++) {
		lli[i] = *(--upper_bound(all(h[c[i]]), i));
		rli[i] = *upper_bound(all(h[c[i]]), i);
	}
	vector <int> dod;
	for (int i = 0; i < n-1; i++) dod.pb(rli[i]);
	T.init(0, 0, dod);
	for (int i = 0; i < n-1; i++) {
		if (lli[i] == -1) {
			dod.pb(-1);
			continue;
		}
		dod.pb(T.get(1, lli[i], i-1, i+1));
		if (dod[i] == -1) dod[i] = n;
	}
	T.init(1, inf, dod);
	for (int i = 0; i < n; i++) {
		for (auto p : qu2[i]) {
			if (T.query(1, i, p.F-1) >= i) res[p.S] = 1;
		}
	}
	
	for (int i = 0; i < n-1; i++) dod.pb(lli[i]);
	T.init(1, inf, dod);
	for (int i = 0; i < n-1; i++) {
		if (rli[i] == n) {
			dod.pb(n);
			continue;
		}
		dod.pb(T.get(1, i+1, rli[i]-1, i));
	}
	T.init(0, 0, dod);
	for (int i = 0; i < n; i++) {
		for (auto p : qu1[i]) {
			if (T.query(1, p.F, i-1) < i) res[p.S] = 1;
		}
	}
	for (int i = 0; i < q; i++) cout << (res[i] ? "YES\n" : "NO\n");

	return 0;
}

Compilation message

long_mansion.cpp: In member function 'void Tr::init(int, int, std::vector<int>&)':
long_mansion.cpp:34:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   for (int i = 0; i < v.size(); i++) t[i+ofs] = v[i];
      |                   ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 63572 KB Output is correct
2 Correct 29 ms 63836 KB Output is correct
3 Correct 32 ms 64084 KB Output is correct
4 Correct 29 ms 63580 KB Output is correct
5 Correct 31 ms 63580 KB Output is correct
6 Correct 29 ms 63552 KB Output is correct
7 Correct 29 ms 63732 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 63572 KB Output is correct
2 Correct 29 ms 63836 KB Output is correct
3 Correct 32 ms 64084 KB Output is correct
4 Correct 29 ms 63580 KB Output is correct
5 Correct 31 ms 63580 KB Output is correct
6 Correct 29 ms 63552 KB Output is correct
7 Correct 29 ms 63732 KB Output is correct
8 Correct 162 ms 83796 KB Output is correct
9 Correct 161 ms 83544 KB Output is correct
10 Correct 165 ms 85584 KB Output is correct
11 Correct 174 ms 85844 KB Output is correct
12 Correct 144 ms 82776 KB Output is correct
13 Correct 127 ms 84820 KB Output is correct
14 Correct 124 ms 84452 KB Output is correct
15 Correct 125 ms 84368 KB Output is correct
16 Correct 122 ms 83964 KB Output is correct
17 Correct 121 ms 85148 KB Output is correct
18 Correct 123 ms 84308 KB Output is correct
19 Correct 125 ms 84824 KB Output is correct
20 Correct 124 ms 82004 KB Output is correct
21 Correct 123 ms 83984 KB Output is correct
22 Correct 127 ms 85076 KB Output is correct
23 Correct 125 ms 84092 KB Output is correct
24 Correct 145 ms 84228 KB Output is correct
25 Correct 132 ms 84120 KB Output is correct
26 Correct 139 ms 83792 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 101328 KB Output is correct
2 Correct 316 ms 100812 KB Output is correct
3 Correct 303 ms 100532 KB Output is correct
4 Correct 324 ms 101076 KB Output is correct
5 Correct 301 ms 101044 KB Output is correct
6 Correct 248 ms 97740 KB Output is correct
7 Correct 251 ms 98432 KB Output is correct
8 Correct 265 ms 98360 KB Output is correct
9 Correct 246 ms 98512 KB Output is correct
10 Correct 245 ms 98512 KB Output is correct
11 Correct 244 ms 98512 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 63572 KB Output is correct
2 Correct 29 ms 63836 KB Output is correct
3 Correct 32 ms 64084 KB Output is correct
4 Correct 29 ms 63580 KB Output is correct
5 Correct 31 ms 63580 KB Output is correct
6 Correct 29 ms 63552 KB Output is correct
7 Correct 29 ms 63732 KB Output is correct
8 Correct 162 ms 83796 KB Output is correct
9 Correct 161 ms 83544 KB Output is correct
10 Correct 165 ms 85584 KB Output is correct
11 Correct 174 ms 85844 KB Output is correct
12 Correct 144 ms 82776 KB Output is correct
13 Correct 127 ms 84820 KB Output is correct
14 Correct 124 ms 84452 KB Output is correct
15 Correct 125 ms 84368 KB Output is correct
16 Correct 122 ms 83964 KB Output is correct
17 Correct 121 ms 85148 KB Output is correct
18 Correct 123 ms 84308 KB Output is correct
19 Correct 125 ms 84824 KB Output is correct
20 Correct 124 ms 82004 KB Output is correct
21 Correct 123 ms 83984 KB Output is correct
22 Correct 127 ms 85076 KB Output is correct
23 Correct 125 ms 84092 KB Output is correct
24 Correct 145 ms 84228 KB Output is correct
25 Correct 132 ms 84120 KB Output is correct
26 Correct 139 ms 83792 KB Output is correct
27 Correct 324 ms 101328 KB Output is correct
28 Correct 316 ms 100812 KB Output is correct
29 Correct 303 ms 100532 KB Output is correct
30 Correct 324 ms 101076 KB Output is correct
31 Correct 301 ms 101044 KB Output is correct
32 Correct 248 ms 97740 KB Output is correct
33 Correct 251 ms 98432 KB Output is correct
34 Correct 265 ms 98360 KB Output is correct
35 Correct 246 ms 98512 KB Output is correct
36 Correct 245 ms 98512 KB Output is correct
37 Correct 244 ms 98512 KB Output is correct
38 Correct 631 ms 139112 KB Output is correct
39 Correct 626 ms 150244 KB Output is correct
40 Correct 489 ms 126400 KB Output is correct
41 Correct 565 ms 149220 KB Output is correct
42 Correct 265 ms 97480 KB Output is correct
43 Correct 229 ms 97720 KB Output is correct
44 Correct 349 ms 112076 KB Output is correct
45 Correct 356 ms 111860 KB Output is correct
46 Correct 352 ms 111824 KB Output is correct
47 Correct 266 ms 97748 KB Output is correct
48 Correct 239 ms 98256 KB Output is correct
49 Correct 324 ms 113184 KB Output is correct
50 Correct 368 ms 112584 KB Output is correct
51 Correct 392 ms 111812 KB Output is correct
52 Correct 281 ms 111420 KB Output is correct
53 Correct 405 ms 125276 KB Output is correct
54 Correct 409 ms 137412 KB Output is correct
55 Correct 359 ms 125124 KB Output is correct