oj.uz

Submission #801955

# Submission time Handle Problem Language Result Execution time Memory
801955 2023-08-02T08:41:22 Z vjudge1 Long Mansion (JOI17_long_mansion) C++17
0 / 100
 467 ms 17152 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;
    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){
            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]);
    }
    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

long_mansion.cpp: In function 'void solve()':
long_mansion.cpp:82:16: warning: unused variable 'j' [-Wunused-variable]
   82 |     ll q , i , j , m , z , s  = 0, f, l , r , k , x , y ,  mx = -1;
      |                ^
long_mansion.cpp:82:20: warning: unused variable 'm' [-Wunused-variable]
   82 |     ll q , i , j , m , z , s  = 0, f, l , r , k , x , y ,  mx = -1;
      |                    ^
long_mansion.cpp:82:24: warning: unused variable 'z' [-Wunused-variable]
   82 |     ll q , i , j , m , z , s  = 0, f, l , r , k , x , y ,  mx = -1;
      |                        ^
long_mansion.cpp:82:28: warning: unused variable 's' [-Wunused-variable]
   82 |     ll q , i , j , m , z , s  = 0, f, l , r , k , x , y ,  mx = -1;
      |                            ^
long_mansion.cpp:82:36: warning: unused variable 'f' [-Wunused-variable]
   82 |     ll q , i , j , m , z , s  = 0, f, l , r , k , x , y ,  mx = -1;
      |                                    ^
long_mansion.cpp:82:39: warning: unused variable 'l' [-Wunused-variable]
   82 |     ll q , i , j , m , z , s  = 0, f, l , r , k , x , y ,  mx = -1;
      |                                       ^
long_mansion.cpp:82:43: warning: unused variable 'r' [-Wunused-variable]
   82 |     ll q , i , j , m , z , s  = 0, f, l , r , k , x , y ,  mx = -1;
      |                                           ^
long_mansion.cpp:82:47: warning: unused variable 'k' [-Wunused-variable]
   82 |     ll q , i , j , m , z , s  = 0, f, l , r , k , x , y ,  mx = -1;
      |                                               ^
long_mansion.cpp:82:60: warning: unused variable 'mx' [-Wunused-variable]
   82 |     ll q , i , j , m , z , s  = 0, f, l , r , k , x , y ,  mx = -1;
      |                                                            ^~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 75.0

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