Submission #431320

#	Time	Username	Problem	Language	Result	Execution time	Memory
431320		maomao90	Long Mansion (JOI17_long_mansion)	C++17	10 / 100	3075 ms	21792 KiB

long_mansion

#include <bits/stdc++.h> 
using namespace std;

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb emplace_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;

#ifdef DEBUG
#define debug(args...) _debug(args)
void _debug(const char* format, ...) {
		va_list args;
			va_start(args, format);
				vprintf(format, args);
					va_end(args);
}
#else
#define debug(args...)
#endif

#define INF 1000000005
#define LINF 1000000000000000005
#define MOD 1000000007
#define MAXN 500005

struct thing {
	int x, y, i;
	bool operator< (const thing& o) const {
		return MP(x, y) < MP(o.x, o.y);
	}
};

int n;
int c[MAXN];
int b[MAXN];
vi a[MAXN];
int q;
ii range[MAXN];
bool ans[MAXN], key[MAXN];

int main() {
	scanf("%d", &n);
	REP (i, 1, n) {
		scanf("%d", &c[i]);
	}
	REP (i, 1, n + 1) {
		scanf("%d", &b[i]);
		a[i].resize(b[i] + 5);
		REP (j, 1, b[i] + 1) {
			scanf("%d", &a[i][j]);
		}
	}
	REP (i, 1, n + 1) {
		int l = i, r = i;
		vi tmp;
		REP (j, 1, b[l] + 1) {
			key[a[l][j]] = 1;
			tmp.pb(a[l][j]);
		}
		while (1) {
			bool prog = 0;
			while (l != 1 && key[c[l - 1]]) {
				l--;
				REP (j, 1, b[l] + 1) {
					key[a[l][j]] = 1;
					tmp.pb(a[l][j]);
				}
				prog = 1;
			}
			while (r != n && key[c[r]]) {
				r++;
				REP (j, 1, b[r] + 1) {
					key[a[r][j]] = 1;
					tmp.pb(a[r][j]);
				}
				prog = 1;
			}
			if (!prog) break;
		}
		for (int &j : tmp) {
			key[j] = 0;
		}
		debug("%d: %d %d\n", i, l, r);
		range[i] = MP(l, r);
	}
	scanf("%d", &q);
	REP (i, 0, q) {
		int x, y; scanf("%d%d", &x, &y);
		ans[i] = y >= range[x].FI && y <= range[x].SE;
	}
	REP (i, 0, q) {
		if (ans[i]) {
			printf("YES\n");
		} else {
			printf("NO\n");
		}
	}
	return 0;
}

/*
5
1 2 3 4
2 2 3
1 1
1 1
1 3
1 4
4
2 4
4 2
1 5
5 3
*/

Compilation message (stderr)

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
long_mansion.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |   scanf("%d", &c[i]);
      |   ~~~~~^~~~~~~~~~~~~
long_mansion.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |   scanf("%d", &b[i]);
      |   ~~~~~^~~~~~~~~~~~~
long_mansion.cpp:66:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |    scanf("%d", &a[i][j]);
      |    ~~~~~^~~~~~~~~~~~~~~~
long_mansion.cpp:102:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
long_mansion.cpp:104:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |   int x, y; scanf("%d%d", &x, &y);
      |             ~~~~~^~~~~~~~~~~~~~~~

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