oj.uz

Submission #257381

# Submission time Handle Problem Language Result Execution time Memory
257381 2020-08-04T08:05:06 Z YJU Long Mansion (JOI17_long_mansion) C++14
0 / 100
 3000 ms 31096 KB 
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll MOD=1e9+7;
const ll N=2e5+5;
const ld pi=3.14159265359;
const ll INF=(1LL<<62);
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(a) (ll)a.size()

ll n,c[N],t,x,y,goR[N],q;
pll range[N];
set<ll> exi[N];

bool in(ll L,ll R,ll ty){
	auto it=exi[ty].lwb(L);
	if(it!=exi[ty].end()&&*it<=R)return 1;
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n;
	REP1(i,n-1)cin>>c[i];
	REP1(i,n){
		cin>>t;
		while(t--)cin>>x,exi[x].insert(i);
	}
	for(ll i=n;i>=1;i--){
		goR[i]=i;
		while(in(i,goR[i],c[goR[i]])){
			++goR[i];
			goR[i]=goR[goR[i]];
		}
		range[i]=mp(i,goR[i]);
	}
	for(ll i=2;i<=n;i++){
		while(1){
			if(range[i].X>1&&in(range[i].X,range[i].Y,c[range[i].X-1])){
				ll tt=range[i].X-1;
				range[i].X=min(range[i].X,range[tt].X);
				range[i].Y=max(range[i].Y,range[tt].Y);
			}else if(range[i].Y<n&&in(range[i].X,range[i].Y,c[range[i].Y])){
				++range[i].Y;
				range[i].Y=goR[range[i].Y];
			}else break;
		}
	}
	cin>>q;
	while(q--){
		cin>>x>>y;
		cout<<(range[x].X<=y&&range[x].Y>=y?"YES\n":"NO\n");
	}
	return 0;
}

Compilation message

long_mansion.cpp:9:18: warning: overflow in implicit constant conversion [-Woverflow]
 const ll INF=(1LL<<62);
              ~~~~^~~~~
long_mansion.cpp: In function 'bool in(ll, ll, ll)':
long_mansion.cpp:27:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3058 ms 9984 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3058 ms 9984 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3080 ms 31096 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3058 ms 9984 KB Time limit exceeded
2 Halted 0 ms 0 KB -