Submission #1026639

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026639		lovrot	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	409 ms	83660 KiB

long_mansion

#include <cstdio>
#include <vector>
#include <set>
#include <cassert>
#include <algorithm> 
#include <cstring> 

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int LOG = 19;
const int N = 1 << LOG;
const int OO = 2e9 + 10;

int n, c[N];
vector<int> klj[N];

int lst[N], lf[N], rg[N];
int L[N], R[N];
vector<int> g[N];
set<int> act, s;

int t[2 * N];

void update(int u, int w) { 
	u += N;
	t[u] = w;
	for(u >>= 1; u; u >>= 1) { 
		t[u] = max(t[2 * u], t[2 * u + 1]);
	}
}

int query(int l, int r, int w, int u = 1, int lo = 0, int hi = N) {
	if(r <= lo || hi <= l || t[u] < w) { return -1; }
	if(lo + 1 == hi) { return lo; }
	int mi = (lo + hi) / 2;	
	int res = query(l, r, w, 2 * u + 1, mi, hi);
	if(res == -1) { return query(l, r, w, 2 * u, lo, mi); }
	return res;
}

int main() { 
	scanf("%d", &n);
	for(int i = 1; i < n; ++i) { 
		scanf("%d", c + i);
	}
	for(int i = 1; i <= n; ++i) { 
		int b; scanf("%d", &b);
		for(; b--; ) { 
			int x; scanf("%d", &x);
			klj[i].PB(x);
		}
	}

	lf[n + 1] = lf[1] = 0;
	g[0].PB(n + 1);
	g[0].PB(1);
	for(int i = 1; i <= n; ++i) { 
		if(i > 1) {
			lf[i] = lst[c[i -  1]];
			g[lf[i]].PB(i);
		}
		for(int x : klj[i]) { 
			lst[x] = i;
		}
	}

	for(int i = 1; i <= n; ++i) { 
		lst[i] = n + 1;
	}
	rg[0] = rg[n] = n + 1;
	for(int i = n; i >= 1; --i) { 
		if(i < n) { 
			rg[i] = lst[c[i]];
		}
		for(int x : klj[i]) { 
			lst[x] = i;
		}
	}

	for(int x : g[0]) { 
		act.insert(x);
	}

	for(int i = 1; i <= n; ++i) {
		if(act.find(i) != act.end()) { 
			act.erase(i);
		} else if(s.find(i) != s.end()) { 
			s.erase(i);
		}

		update(i - 1, rg[i - 1]);
		for(; !act.empty() && *(act.begin()) <= rg[i - 1]; act.erase(act.begin())) { 
//			printf("a->s %d\n", *act.begin());
			s.insert(*act.begin());
		}

		assert(!s.empty());
		R[i] = *s.begin();
		L[i] = query(lf[R[i]], n + 1, R[i]);
//		printf("%d %d (%d, %d)\n", L[i], R[i], lf[i], rg[i]);

		for(int x : g[i]) {
			act.insert(x);
		}
	}

	int q; scanf("%d", &q);
	for(; q--; ) { 
		int x, y; scanf("%d%d", &x, &y);
		printf("%s\n", L[x] < y && y < R[x] ? "YES" : "NO");
	}
	return 0;
}

Compilation message (stderr)

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
long_mansion.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |   scanf("%d", c + i);
      |   ~~~~~^~~~~~~~~~~~~
long_mansion.cpp:54:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |   int b; scanf("%d", &b);
      |          ~~~~~^~~~~~~~~~
long_mansion.cpp:56:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |    int x; scanf("%d", &x);
      |           ~~~~~^~~~~~~~~~
long_mansion.cpp:114:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |  int q; scanf("%d", &q);
      |         ~~~~~^~~~~~~~~~
long_mansion.cpp:116:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |   int x, y; scanf("%d%d", &x, &y);
      |             ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 75 / 75