oj.uz

Submission #536911

# Submission time Handle Problem Language Result Execution time Memory
536911 2022-03-14T07:15:41 Z yungyao Long Mansion (JOI17_long_mansion) C++17
10 / 100
 3000 ms 26556 KB 
/*


weak        weak  we      ak   we  akwea        weak  we
  weak    weak    we      ak   weak    weak    we  ak we
    weakweak      we      ak   wea       ak   we    akwe
      wea         we      ak   we        ak   we    akwe
      wea         we      ak   we        ak   we    akwe
      wea          eak  weak   we        ak    we  ak we
      wea            wea  ak   we        ak     weak  we
                                                      we
we      ak     wea  ak       weak                     we
 we    ak    wea  weak     wea  eak                   we
  we  ak    we      ak   wea      wea         we      we
   weak     we      ak   we        we         we      we
    we      we      ak   we        we         we      we
   we        wea  weak    wea    wea          weak  weak
weak           wea  akw      weak                weak


*/
//#define _GLIBCXX_DEBUG //is only used when couldn't find bug
using namespace std;
#pragma GCC optimize ("Ofast")
//headers
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <utility>
#include <bitset>
#include <set>
#include <string>
#include <stack>
#include <iomanip>
#include <map>
#include <memory.h>
#include <deque>
#include <time.h>
#include <assert.h>
#include <unordered_map>
#include <unordered_set>
#include <sstream>

//defines
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
typedef vector<int> vi;
typedef vector<LL> vl;
typedef vector<vector<int>> vvi;
typedef vector<vector<LL>> vvl;
#define pb push_back
#define F first
#define S second
#define mid (LB+RB)/2
#define mkp make_pair

//iterators
#define iter(x) x.begin(),x.end()
#define aiter(a,n) a,a+n

//loops
#define REP(n) for (int ___=n > 0 ? n : 0;___--;)
#define REP0(i,n) for (int i=0,___=n;i<___;++i)
#define REP1(i,n) for (int i=1,___=n;i<=___;++i)
#define MEM(e,val) memset (e,val,sizeof(e))

/*
When he said Super Idol??摰寥瘝∩????急?甇????瘝∩??€?潛??105 簞C??皛湔輕皜滲?擐偌雿??乩????舐頝€?隡蝚???韏瑚?隞?賭?頧餉?憭梯揖撖寞╪?喟??抒?銝€?港??暹敺?敹?敶?撖寞?霂港?????曄?霈拇??亙??Ｚ蕭?芸楛?╪?喲???芋??
I really felt that.


every one is so dian except me
still too weak ?拙?
*/

//IO
#include <cstdio>
#include <iostream>
#include <fstream>
#define want_to_be_more_dian ios_base::sync_with_stdio(false),cin.tie(0);

//pbds
/*
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
using namespace __gnu_pbds;
//tree <pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update>;
*/

//constants
#include <climits>
const int maxn = 5e5+10,mod = 0;
const long long inf = 0;
const double eps = 0;

//workspace

int c[maxn];
int fr[maxn], fl[maxn];
vector <int> key[maxn];
int clo[maxn];
pii seg[maxn];

inline void solve(){
	int n, q;

	cin >> n;
	REP1(i, n-1) cin >> c[i];
	REP1(i, n){
		int k;

		cin >> k;
		key[i].resize(k);
		for (auto &x:key[i]) cin >> x;
	}
	REP1(i, n) clo[i] = n+1;
	for (auto &x:key[n]) clo[x] = n;
	for (int i=n-1;i;--i){
		fr[i] = clo[c[i]];
		for (auto &x:key[i]) clo[x] = i;
	}
	REP1(i, n) clo[i] = 0;
	for (auto &x:key[1]) clo[x] = 1;
	for (int i=2;i<=n;++i){
		fl[i] = clo[c[i-1]];
		for (auto &x:key[i]) clo[x] = i;
	}
	
	fr[0] = n+1; fl[n+1] = 0;
	REP1(i, n){
		seg[i] = mkp(i, i);
		while (true){
			if (fr[seg[i].F-1] <= seg[i].S) --seg[i].F;
			else if (fl[seg[i].S+1] >= seg[i].F) ++seg[i].S;
			else break;
		}
	}
	cin >> q;
	REP(q){
		int a, b;

		cin >> a >> b;
		if (b >= seg[a].F and b <= seg[a].S) cout << "YES\n";
		else cout << "NO\n";
	}
}

signed main(){
	want_to_be_more_dian
	//int t,i=1; for (int ;cin;)//use in multi-testcases and end in EOF problems
	//int t,i=1; for (cin >> t;i<=t;++i)//use in multi-testcases problems
	//cout << "Case #" << i << ": ",//use in Google, FB competitions
	solve();//always used
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12244 KB Output is correct
2 Correct 11 ms 12356 KB Output is correct
3 Correct 22 ms 12424 KB Output is correct
4 Correct 9 ms 12244 KB Output is correct
5 Correct 11 ms 12244 KB Output is correct
6 Correct 10 ms 12196 KB Output is correct
7 Correct 9 ms 12176 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12244 KB Output is correct
2 Correct 11 ms 12356 KB Output is correct
3 Correct 22 ms 12424 KB Output is correct
4 Correct 9 ms 12244 KB Output is correct
5 Correct 11 ms 12244 KB Output is correct
6 Correct 10 ms 12196 KB Output is correct
7 Correct 9 ms 12176 KB Output is correct
8 Correct 94 ms 18108 KB Output is correct
9 Correct 91 ms 17992 KB Output is correct
10 Correct 95 ms 18360 KB Output is correct
11 Correct 104 ms 18804 KB Output is correct
12 Correct 89 ms 17600 KB Output is correct
13 Correct 94 ms 18300 KB Output is correct
14 Correct 92 ms 18240 KB Output is correct
15 Correct 94 ms 18228 KB Output is correct
16 Correct 92 ms 18108 KB Output is correct
17 Correct 91 ms 18252 KB Output is correct
18 Correct 98 ms 18280 KB Output is correct
19 Correct 90 ms 18252 KB Output is correct
20 Correct 90 ms 18256 KB Output is correct
21 Correct 94 ms 18116 KB Output is correct
22 Correct 91 ms 18120 KB Output is correct
23 Correct 96 ms 17992 KB Output is correct
24 Correct 93 ms 18004 KB Output is correct
25 Correct 96 ms 17972 KB Output is correct
26 Correct 91 ms 17984 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 826 ms 26556 KB Output is correct
2 Correct 1639 ms 26392 KB Output is correct
3 Execution timed out 3081 ms 19016 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12244 KB Output is correct
2 Correct 11 ms 12356 KB Output is correct
3 Correct 22 ms 12424 KB Output is correct
4 Correct 9 ms 12244 KB Output is correct
5 Correct 11 ms 12244 KB Output is correct
6 Correct 10 ms 12196 KB Output is correct
7 Correct 9 ms 12176 KB Output is correct
8 Correct 94 ms 18108 KB Output is correct
9 Correct 91 ms 17992 KB Output is correct
10 Correct 95 ms 18360 KB Output is correct
11 Correct 104 ms 18804 KB Output is correct
12 Correct 89 ms 17600 KB Output is correct
13 Correct 94 ms 18300 KB Output is correct
14 Correct 92 ms 18240 KB Output is correct
15 Correct 94 ms 18228 KB Output is correct
16 Correct 92 ms 18108 KB Output is correct
17 Correct 91 ms 18252 KB Output is correct
18 Correct 98 ms 18280 KB Output is correct
19 Correct 90 ms 18252 KB Output is correct
20 Correct 90 ms 18256 KB Output is correct
21 Correct 94 ms 18116 KB Output is correct
22 Correct 91 ms 18120 KB Output is correct
23 Correct 96 ms 17992 KB Output is correct
24 Correct 93 ms 18004 KB Output is correct
25 Correct 96 ms 17972 KB Output is correct
26 Correct 91 ms 17984 KB Output is correct
27 Correct 826 ms 26556 KB Output is correct
28 Correct 1639 ms 26392 KB Output is correct
29 Execution timed out 3081 ms 19016 KB Time limit exceeded
30 Halted 0 ms 0 KB -