제출 #1026010

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1026010		Tob	Long Mansion (JOI17_long_mansion)	C++14	100 / 100	631 ms	150244 KiB

long_mansion

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 75 / 75