| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 801985 | 2023-08-02T08:54:38 Z | vjudge1 | Long Mansion (JOI17_long_mansion) | C++17 | 2850 ms | 76372 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 = 1e6 + 9 , mod = 1e9 + 7;
ll d[N] = {} , a[N] = {}, dp[N] = {}, b[N] , c[N] , le[N] , ri[N];
vector<int>v[N / 2] ;
const int L = (1 << 18);
ll seg[2000009] , 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
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 10 ms | 12296 KB | Output is correct |
| 2 | Correct | 12 ms | 12372 KB | Output is correct |
| 3 | Correct | 21 ms | 12628 KB | Output is correct |
| 4 | Correct | 10 ms | 12244 KB | Output is correct |
| 5 | Correct | 10 ms | 12244 KB | Output is correct |
| 6 | Correct | 12 ms | 12304 KB | Output is correct |
| 7 | Correct | 11 ms | 12304 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 10 ms | 12296 KB | Output is correct |
| 2 | Correct | 12 ms | 12372 KB | Output is correct |
| 3 | Correct | 21 ms | 12628 KB | Output is correct |
| 4 | Correct | 10 ms | 12244 KB | Output is correct |
| 5 | Correct | 10 ms | 12244 KB | Output is correct |
| 6 | Correct | 12 ms | 12304 KB | Output is correct |
| 7 | Correct | 11 ms | 12304 KB | Output is correct |
| 8 | Correct | 89 ms | 14184 KB | Output is correct |
| 9 | Correct | 79 ms | 14056 KB | Output is correct |
| 10 | Correct | 94 ms | 14344 KB | Output is correct |
| 11 | Correct | 89 ms | 14596 KB | Output is correct |
| 12 | Correct | 73 ms | 14104 KB | Output is correct |
| 13 | Correct | 87 ms | 14208 KB | Output is correct |
| 14 | Correct | 94 ms | 14192 KB | Output is correct |
| 15 | Correct | 78 ms | 14280 KB | Output is correct |
| 16 | Correct | 88 ms | 14472 KB | Output is correct |
| 17 | Correct | 80 ms | 14172 KB | Output is correct |
| 18 | Correct | 82 ms | 14260 KB | Output is correct |
| 19 | Correct | 76 ms | 14284 KB | Output is correct |
| 20 | Correct | 82 ms | 14444 KB | Output is correct |
| 21 | Correct | 84 ms | 14532 KB | Output is correct |
| 22 | Correct | 80 ms | 14372 KB | Output is correct |
| 23 | Correct | 88 ms | 14156 KB | Output is correct |
| 24 | Correct | 85 ms | 14056 KB | Output is correct |
| 25 | Correct | 82 ms | 14124 KB | Output is correct |
| 26 | Correct | 82 ms | 14176 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 524 ms | 24220 KB | Output is correct |
| 2 | Correct | 508 ms | 24236 KB | Output is correct |
| 3 | Correct | 514 ms | 24168 KB | Output is correct |
| 4 | Correct | 536 ms | 24244 KB | Output is correct |
| 5 | Correct | 510 ms | 24200 KB | Output is correct |
| 6 | Correct | 490 ms | 23756 KB | Output is correct |
| 7 | Correct | 515 ms | 23908 KB | Output is correct |
| 8 | Correct | 505 ms | 23928 KB | Output is correct |
| 9 | Correct | 527 ms | 23920 KB | Output is correct |
| 10 | Correct | 524 ms | 23908 KB | Output is correct |
| 11 | Correct | 514 ms | 23872 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 10 ms | 12296 KB | Output is correct |
| 2 | Correct | 12 ms | 12372 KB | Output is correct |
| 3 | Correct | 21 ms | 12628 KB | Output is correct |
| 4 | Correct | 10 ms | 12244 KB | Output is correct |
| 5 | Correct | 10 ms | 12244 KB | Output is correct |
| 6 | Correct | 12 ms | 12304 KB | Output is correct |
| 7 | Correct | 11 ms | 12304 KB | Output is correct |
| 8 | Correct | 89 ms | 14184 KB | Output is correct |
| 9 | Correct | 79 ms | 14056 KB | Output is correct |
| 10 | Correct | 94 ms | 14344 KB | Output is correct |
| 11 | Correct | 89 ms | 14596 KB | Output is correct |
| 12 | Correct | 73 ms | 14104 KB | Output is correct |
| 13 | Correct | 87 ms | 14208 KB | Output is correct |
| 14 | Correct | 94 ms | 14192 KB | Output is correct |
| 15 | Correct | 78 ms | 14280 KB | Output is correct |
| 16 | Correct | 88 ms | 14472 KB | Output is correct |
| 17 | Correct | 80 ms | 14172 KB | Output is correct |
| 18 | Correct | 82 ms | 14260 KB | Output is correct |
| 19 | Correct | 76 ms | 14284 KB | Output is correct |
| 20 | Correct | 82 ms | 14444 KB | Output is correct |
| 21 | Correct | 84 ms | 14532 KB | Output is correct |
| 22 | Correct | 80 ms | 14372 KB | Output is correct |
| 23 | Correct | 88 ms | 14156 KB | Output is correct |
| 24 | Correct | 85 ms | 14056 KB | Output is correct |
| 25 | Correct | 82 ms | 14124 KB | Output is correct |
| 26 | Correct | 82 ms | 14176 KB | Output is correct |
| 27 | Correct | 524 ms | 24220 KB | Output is correct |
| 28 | Correct | 508 ms | 24236 KB | Output is correct |
| 29 | Correct | 514 ms | 24168 KB | Output is correct |
| 30 | Correct | 536 ms | 24244 KB | Output is correct |
| 31 | Correct | 510 ms | 24200 KB | Output is correct |
| 32 | Correct | 490 ms | 23756 KB | Output is correct |
| 33 | Correct | 515 ms | 23908 KB | Output is correct |
| 34 | Correct | 505 ms | 23928 KB | Output is correct |
| 35 | Correct | 527 ms | 23920 KB | Output is correct |
| 36 | Correct | 524 ms | 23908 KB | Output is correct |
| 37 | Correct | 514 ms | 23872 KB | Output is correct |
| 38 | Correct | 1256 ms | 68084 KB | Output is correct |
| 39 | Correct | 1544 ms | 76372 KB | Output is correct |
| 40 | Correct | 925 ms | 58248 KB | Output is correct |
| 41 | Correct | 2850 ms | 70780 KB | Output is correct |
| 42 | Correct | 472 ms | 31252 KB | Output is correct |
| 43 | Correct | 469 ms | 31164 KB | Output is correct |
| 44 | Correct | 960 ms | 43728 KB | Output is correct |
| 45 | Correct | 1037 ms | 43776 KB | Output is correct |
| 46 | Correct | 994 ms | 43868 KB | Output is correct |
| 47 | Correct | 566 ms | 31180 KB | Output is correct |
| 48 | Correct | 537 ms | 30972 KB | Output is correct |
| 49 | Correct | 1096 ms | 43736 KB | Output is correct |
| 50 | Correct | 1086 ms | 43760 KB | Output is correct |
| 51 | Correct | 1116 ms | 44152 KB | Output is correct |
| 52 | Correct | 892 ms | 43268 KB | Output is correct |
| 53 | Correct | 1363 ms | 57312 KB | Output is correct |
| 54 | Correct | 1737 ms | 67248 KB | Output is correct |
| 55 | Correct | 1321 ms | 57548 KB | Output is correct |