oj.uz

Submission #125286

# Submission time Handle Problem Language Result Execution time Memory
125286 2019-07-05T04:45:21 Z 구재현(#3066) Long Mansion (JOI17_long_mansion) C++14
0 / 100
 20 ms 14200 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500005;
using lint = long long;
using pi = pair<int, int>;

int n, c[MAXN];
vector<int> key_loc[MAXN];

int L[MAXN], R[MAXN];
int up[MAXN], dn[MAXN];
pi rng[MAXN];

int main(){
	scanf("%d",&n);
	if(n > 10000) return 0;
	for(int i=1; i<n; i++) scanf("%d",&c[i]);
	for(int i=1; i<=n; i++){
		int x; scanf("%d",&x);
		for(int j=0; j<x; j++){
			int y; scanf("%d",&y);
			key_loc[y].push_back(i);
		}
	}
	for(int i=1; i<n; i++){
		auto p = lower_bound(key_loc[c[i]].begin(), key_loc[c[i]].end(), i + 1);
		if(p == key_loc[c[i]].end()) R[i] = n + 1;
		else R[i] = *p;
		if(p == key_loc[c[i]].begin()) L[i] = 0;
		else L[i] = *prev(p);
	}
	R[0] = n + 1;
	L[n + 1] = 0;
	fill(rng + 1, rng + n + 1, pi(1, n));
	memset(dn, 0x3f, sizeof(dn));
	for(int i=1; i<=n; i++){
		for(int j=i; j<R[i-1]; j++){
			if(L[j] < i){
				up[i] = max(up[i], j);
			}
		}
	}
	for(int i=1; i<=n; i++){
		for(int j=L[i] + 1; j<=i; j++){
			if(R[j - 1] > i){
				dn[i] = min(dn[i], j);
			}
		}
	}
	vector<pi> stk;
	for(int i=1; i<=n; i++){
		while(!stk.empty() && stk.back().first <= max(i, up[i])){
			stk.pop_back();
		}
		if(up[i] >= i) stk.emplace_back(up[i], i);
		if(stk.size()) rng[i].first = stk.back().second;
		else rng[i].first = 1;
	}
	stk.clear();
	for(int i=n; i; i--){
		while(!stk.empty() && stk.back().first >= min(i, dn[i])){
			stk.pop_back();
		}
		if(dn[i] <= i) stk.emplace_back(dn[i], i);
		if(stk.size()) rng[i].second = stk.back().second;
		else rng[i].second = n;
	}
	int q; scanf("%d",&q);
	while(q--){
		int x, y; scanf("%d %d",&x,&y);
		puts(rng[x].first <= y && y <= rng[x].second ? "YES" : "NO");
	}
}

Compilation message

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:15:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
long_mansion.cpp:17:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<n; i++) scanf("%d",&c[i]);
                         ~~~~~^~~~~~~~~~~~
long_mansion.cpp:19:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x; scanf("%d",&x);
          ~~~~~^~~~~~~~~
long_mansion.cpp:21:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int y; scanf("%d",&y);
           ~~~~~^~~~~~~~~
long_mansion.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int q; scanf("%d",&q);
         ~~~~~^~~~~~~~~
long_mansion.cpp:70:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y; scanf("%d %d",&x,&y);
             ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 14200 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 14200 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 12152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 14200 KB Output isn't correct
2 Halted 0 ms 0 KB -