| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 801970 | 2023-08-02T08:49:00 Z | vjudge1 | Long Mansion (JOI17_long_mansion) | C++17 | 529 ms | 24436 KB |
#include <bits/stdc++.h>
using namespace std;
#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define fi first
#define se second
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"
const int N = 1e5 + 9 , mod = 1e9 + 7;
ll d[N] = {} , a[N] = {}, dp[N] = {}, b[N] , c[N] , le[N] , ri[N];
vector<int>v[N] , v1[N];
const int L = (1 << 17);
ll seg[L * 4] , n;
void build(int p, int l, int r) {
if (l == r) {
seg[p] = d[l];
return;
}
int mid = (l + r) >> 1;
build(2 * p, l, mid);
build(2 * p + 1, mid + 1, r);
seg[p] = min(seg[2 * p] , seg[2 * p + 1]);
return;
}
ll Mn = 1e9;
void mn(int i , int l ,int r,int x , int y){
if(l > y || r < x)
return;
if(l >= x && r <= y){
Mn = min(Mn , seg[i]);
return;
}
ll m = (l + r) / 2;
mn(2 * i , l , m , x , y);
mn(2 * i + 1 , m + 1 , r, x , y);
}
ll get(int i , int P){
ll m , l, r;
l = i , r = n;
if(i >= n)
return n;
while(l < r){
m = (l + r ) / 2;
Mn = 1e9;
mn(1 , 1 , n , i , m);
// cout<<i<<" "<<m<<" "<<l<<" "<<r<<" "<<Mn<<"\n";
if(Mn < P){
r = m;
}else {
l = m + 1;
}
}
m = l;
Mn = 1e9;
mn(1 , 1 , n , i , m);
if(Mn >= P)
l++;
return l - 1;
}
void solve(){
ll q , i , j , m , z , s = 0, f, l , r , k , x , y , mx = -1;
cin>>n;
for(i = 1; i < n; i++)
cin>>a[i];
for(i = 1; i <= n; i++){
cin>>x;
while(x--){
cin>>y;
v[i].pb(y);
}
}
for(i = 0; i <= n; i++)
b[i]= n + 1;
for(i = n; i >= 1; i--){
c[i] = b[a[i]];
for(auto to : v[i])
b[to] = i;
}
for(i = 0; i <= n; i++)
b[i] = 0;
for(i = 1; i <= n; i++){
d[i] = b[a[i - 1]];
for(auto to : v[i])
b[to] = i;
}
build(1 , 1 ,n);
deque<ll>v;
for(i = 1; i <= n; i++){
le[i] = ri[i] = i;
ri[i] = get(i + 1 , le[i]);
while(true){
//cout<<c[le[i] - 1]<<" ";
if(v.size() == 0 || (c[le[i] - 1] > ri[i]))
break;
le[i] = v.back();
ri[i] = get(i + 1 , le[i]);
v.pop_back();
}
v.pb(le[i]);
//cout<<le[i]<<" "<<ri[i]<<" "<<v.size()<<"\n";
}
cin>>q;
while(q--){
cin>>x>>y;
if(le[x] <= y && ri[x] >= y)
YES;
else
NO;
}
}
int main(){
TL;
/*
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
*/
int t = 1;
//cin>>t;
while(t--)
{
solve();
}
}
// Author : حسن
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 10 ms | 5460 KB | Output is correct |
| 2 | Correct | 9 ms | 5400 KB | Output is correct |
| 3 | Correct | 16 ms | 5588 KB | Output is correct |
| 4 | Correct | 7 ms | 5312 KB | Output is correct |
| 5 | Correct | 8 ms | 5204 KB | Output is correct |
| 6 | Correct | 7 ms | 5332 KB | Output is correct |
| 7 | Incorrect | 7 ms | 5304 KB | Output isn't correct |
| 8 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 10 ms | 5460 KB | Output is correct |
| 2 | Correct | 9 ms | 5400 KB | Output is correct |
| 3 | Correct | 16 ms | 5588 KB | Output is correct |
| 4 | Correct | 7 ms | 5312 KB | Output is correct |
| 5 | Correct | 8 ms | 5204 KB | Output is correct |
| 6 | Correct | 7 ms | 5332 KB | Output is correct |
| 7 | Incorrect | 7 ms | 5304 KB | Output isn't correct |
| 8 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 478 ms | 17580 KB | Output is correct |
| 2 | Correct | 465 ms | 24328 KB | Output is correct |
| 3 | Correct | 529 ms | 24024 KB | Output is correct |
| 4 | Correct | 491 ms | 24436 KB | Output is correct |
| 5 | Correct | 478 ms | 24436 KB | Output is correct |
| 6 | Correct | 467 ms | 23124 KB | Output is correct |
| 7 | Correct | 497 ms | 22936 KB | Output is correct |
| 8 | Correct | 472 ms | 22832 KB | Output is correct |
| 9 | Correct | 497 ms | 22908 KB | Output is correct |
| 10 | Correct | 503 ms | 22840 KB | Output is correct |
| 11 | Correct | 473 ms | 22844 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 10 ms | 5460 KB | Output is correct |
| 2 | Correct | 9 ms | 5400 KB | Output is correct |
| 3 | Correct | 16 ms | 5588 KB | Output is correct |
| 4 | Correct | 7 ms | 5312 KB | Output is correct |
| 5 | Correct | 8 ms | 5204 KB | Output is correct |
| 6 | Correct | 7 ms | 5332 KB | Output is correct |
| 7 | Incorrect | 7 ms | 5304 KB | Output isn't correct |
| 8 | Halted | 0 ms | 0 KB | - |