Submission #402130

#	Time	Username	Problem	Language	Result	Execution time	Memory
402130		AriaH	Long Mansion (JOI17_long_mansion)	C++11	0 / 100	715 ms	51572 KiB

long_mansion

/** I can do this all day **/

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;

typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define SZ(x)			    		(int)x.size()
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);

const int N = 5e5 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 1e9;
const int LOG = 22;

ll pw(ll a , ll b, ll M)  { return (!b ? 1 : (b & 1 ? (a * pw(a * a % M, b / 2, M)) % M : pw(a * a % M, b / 2, M))); }

short Ans[N];

int n, q, C[N], Z[N], X[N], Y[N], same[N << 2], seg[N << 2], lz[N << 2], last[N], nxt[N], cur[N];

vector < int > keys[N], Q[N];

void build(int v = 1, int tl = 1, int tr = n - 1)
{
	lz[v] = 0;
	same[v] = 0;
	if(tl == tr)
	{
		/*if(last[tl] == -inf)
		{
			seg[v] = -1;
			return;
		}*/
		seg[v] = -last[tl];
		return;
	}
	int mid = (tl + tr) >> 1;
	build(v << 1, tl, mid);
	build(v << 1 | 1, mid + 1, tr);
	seg[v] = max(seg[v << 1], seg[v << 1 | 1]);
}

void S(int v, int tl, int tr)
{
	if(tl == tr || !lz[v]) return;
	seg[v << 1] += lz[v];
	seg[v << 1 | 1] += lz[v];
	lz[v << 1] += lz[v];
	lz[v << 1 | 1] += lz[v];
	lz[v] = 0;
}

void Set(int l, int r, int x, int v = 1, int tl = 1, int tr = n - 1)
{
	S(v, tl, tr);
	if(l > tr || r < tl || l > r) return;
	if(l <= tl && tr <= r && same[v] >= 0)
	{
		lz[v] += x - same[v];
		seg[v] += x - same[v];
		same[v] = x;
		return;
	}
	int mid = (tl + tr) >> 1;
	Set(l, r, x, v << 1, tl, mid);
	Set(l, r, x, v << 1 | 1, mid + 1, tr);
	seg[v] = max(seg[v << 1], seg[v << 1 | 1]);
	same[v] = (same[v << 1] == same[v << 1 | 1]? same[v << 1] : -1);
}

int get(int l, int r, int v = 1, int tl = 1, int tr = n - 1)
{
	S(v, tl, tr);
	if(l > tr || r < tl || l > r) return -inf;
	if(l <= tl && tr <= r) return seg[v];
	int mid = (tl + tr) >> 1;
	return max(get(l, r, v << 1, tl, mid), get(l, r, v << 1 | 1, mid + 1, tr));
}

void solve()
{
	fill(cur, cur + N, -inf);
	for(int i = 1; i <= n; i ++) Q[i].clear();
	for(int i = 1; i <= n; i ++)
	{
		for(auto x : keys[i])
		{
			cur[x] = i;
		}
		/*printf("here i = %d cur : \n", i);
		for(int j = 1; j <= n; j ++)
		{
			printf("%d ", cur[j]);
		}
		printf("\n");*/
		if(i < n) last[i] = cur[C[i]];
	}
	fill(cur, cur + N, inf);
	for(int i = n; i >= 1; i --)
	{
		for(auto x : keys[i]) cur[x] = i;
		if(i > 1) nxt[i - 1] = cur[C[i - 1]];
	}
	/*for(int i = 1; i < n; i ++)
	{
		printf("i = %d last = %d nxt = %d\n", i, last[i], nxt[i]);
	}*/
	build();
	for(int i = 1; i <= q; i ++)
	{
		if(X[i] < Y[i])
		{
			Q[X[i]].push_back(i);
		}
		if(X[i] == Y[i]) Ans[i] = 1;
	}
	/*printf("checking segment i = 0\n");
	for(int i = 1; i < n; i ++) printf("%d ", get(i, i));
	printf("\n");*/
	for(int i = 1; i < n; i ++)
	{
		for(auto now : Q[i])
		{
			if(get(X[now], Y[now] - 1) >= 0) Ans[now] = 0;
			else Ans[now] = 1;
		}
		Set(i + 1, min(n - 1, nxt[i] - 1), i);
		/*printf("i = %d\n", i);
		for(int j = 1; j < n; j ++)
		{
			printf("%d ", get(j, j));
		}
		printf("\n");*/
	}
}

int main()
{
	scanf("%d", &n);
	for(int i = 1; i < n; i ++)
	{
		scanf("%d", &C[i]);
	}
	for(int i = 1; i <= n; i ++)
	{
		scanf("%d", &Z[i]);
		for(int j = 1; j <= Z[i]; j ++)
		{
			int x;
			scanf("%d", &x);
			keys[i].push_back(x);
		}
	}
	scanf("%d", &q);
	for(int i = 1; i <= q; i ++)
	{
		scanf("%d%d", &X[i], &Y[i]);
	}
	solve();
	reverse(C + 1, C + n);
	reverse(keys + 1, keys + n + 1);
	reverse(Z + 1, Z + n + 1);
	for(int i = 1; i <= q; i ++)
	{
		X[i] = n - X[i] + 1;
		Y[i] = n - Y[i] + 1;
	}
	solve();
	for(int i = 1; i <= q; i ++)
	{
		if(Ans[i])
		{
			printf("YES\n");
		}
		else
		{
			printf("NO\n");
		}
	}
	return 0;
}

/** test corner cases(n = 1?) watch for overflow or minus indices **/

Compilation message (stderr)

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:149:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
long_mansion.cpp:152:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |   scanf("%d", &C[i]);
      |   ~~~~~^~~~~~~~~~~~~
long_mansion.cpp:156:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |   scanf("%d", &Z[i]);
      |   ~~~~~^~~~~~~~~~~~~
long_mansion.cpp:160:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  160 |    scanf("%d", &x);
      |    ~~~~~^~~~~~~~~~
long_mansion.cpp:164:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  164 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
long_mansion.cpp:167:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |   scanf("%d%d", &X[i], &Y[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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