oj.uz

Submission #697999

# Submission time Handle Problem Language Result Execution time Memory
697999 2023-02-11T18:41:41 Z urosk Long Mansion (JOI17_long_mansion) C++14
100 / 100
 2517 ms 209352 KB 
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include "bits/stdc++.h"
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll long long
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}

#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;
//using namespace __gnu_pbds;
/*
ll add(ll x,ll y){
    x+=y;
    if(x<0){
        x%=mod;
        x+=mod;
    }else{
        if(x>=mod) x%=mod;
    }
    return x;
}
ll mul(ll a,ll b){
	ll ans = (a*b)%mod;
	if(ans<0) ans+=mod;
	return ans;
}
typedef tree<int,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<int,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll l,ll r){
    return uniform_int_distribution<ll>(l,r)(rng);
}
*/
#define maxn 500005
ll n,q;
ll a[maxn];
ll b[maxn];
set<ll> v[maxn];
set<ll> s[maxn];
ll l[maxn],r[maxn];
ll qx[maxn],qy[maxn];
ll t[2*maxn],ls[2*maxn],rs[2*maxn],root = 0,tsz = 0;
bool ok[maxn];
void upd(ll v,ll tl,ll tr,ll i,ll x){
    if(tl==tr){t[v] = x;return;}
    ll mid = (tl+tr)/2;
    if(i<=mid) upd(ls[v],tl,mid,i,x);
    else upd(rs[v],mid+1,tr,i,x);
    t[v] = min(t[ls[v]],t[rs[v]]);
}
ll get(ll v,ll tl,ll tr,ll l,ll r){
    if(tl>tr||l>tr||r<tl) return llinf;
    if(tl>=l&&tr<=r) return t[v];
    ll mid = (tl+tr)/2;
    return min(get(ls[v],tl,mid,l,r),get(rs[v],mid+1,tr,l,r));
}
void init(ll &v,ll tl,ll tr){
    t[v] = llinf;
    if(!v) v = ++tsz;
    if(tl==tr) return;
    ll mid = (tl+tr)/2;
    init(ls[v],tl,mid);
    init(rs[v],mid+1,tr);
}
bool ans[maxn];
void reshi(bool f){
    init(root,1,n);
    for(ll i = 0;i<=n-1;i++) l[i] = 0;
    for(ll i = 0;i<=n-1;i++) r[i] = n+1;
    /*
    for(ll i = 1;i<=n-1;i++){
        auto it = s[a[i]].lower_bound(i);
        if(it==s[a[i]].end()) continue;
        if((*it)==i){l[i] = r[i] = i;continue;}
        r[i] = (*it);
        if(it!=s[a[i]].begin()){
            it--;
            l[i] = (*it);
        }
    }
    */
    for(ll i = 1;i<=n-1;i++){
        auto it = s[a[i]].upper_bound(i);
        if(it!=s[a[i]].end()) r[i] = (*it);
        if(it!=s[a[i]].begin()){
            it--;
            l[i] = (*it);
        }
    }
    set<pll> st;
    multiset<ll> sl;
    for(ll i = 1;i<=n-1;i++) st.insert({r[i-1],i});
    for(ll i = 1;i<=n-1;i++) sl.insert(i);
    for(ll i = 1;i<=n-1;i++){
        while(sz(st)&&(*st.begin()).fi<=i){
            pll p = (*st.begin());
            ll j = p.sc;
            sl.erase(j);
            st.erase(st.begin());
        }
        auto it = sl.upper_bound(l[i]);
        ll val = llinf;
        if(it!=sl.end()) val = *it;
        upd(root,1,n,i,val);
    }
    for(ll i = 1;i<=q;i++){
        ll x = qx[i],y = qy[i];
        if(x<y&&f) ans[i] = get(root,1,n,x,y-1)>x;
        else if(x>y&&!f){
            x = n-x+1; y = n-y+1;
            ans[i] = get(root,1,n,x,y-1)>x;
        }
    }
}
void tc(){
    cin >> n;
    for(ll i = 1;i<=n-1;i++) cin >> a[i];
    for(ll i = 1;i<=n;i++){
        cin >> b[i];
        for(ll j = 1;j<=b[i];j++){
            ll x; cin >> x;
            v[i].insert(x);
            s[x].insert(i);
        }
    }
    cin >> q;
    for(ll i = 1;i<=q;i++) cin >> qx[i] >> qy[i];
    reshi(1);
    reverse(a+1,a+n);
    reverse(v+1,v+1+n);
    for(ll i = 1;i<=n;i++) s[i].clear();
    for(ll i = 1;i<=n;i++){
        for(ll x : v[i]) s[x].insert(i);
    }
    reshi(0);
    for(ll i = 1;i<=q;i++){
        if(ans[i]) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
}
int main(){
	daj_mi_malo_vremena
    int t; t = 1;
    while(t--){
        tc();
    }
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 48328 KB Output is correct
2 Correct 29 ms 48476 KB Output is correct
3 Correct 30 ms 48852 KB Output is correct
4 Correct 29 ms 48188 KB Output is correct
5 Correct 28 ms 48252 KB Output is correct
6 Correct 26 ms 48208 KB Output is correct
7 Correct 26 ms 48208 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 48328 KB Output is correct
2 Correct 29 ms 48476 KB Output is correct
3 Correct 30 ms 48852 KB Output is correct
4 Correct 29 ms 48188 KB Output is correct
5 Correct 28 ms 48252 KB Output is correct
6 Correct 26 ms 48208 KB Output is correct
7 Correct 26 ms 48208 KB Output is correct
8 Correct 252 ms 62348 KB Output is correct
9 Correct 222 ms 62260 KB Output is correct
10 Correct 231 ms 62836 KB Output is correct
11 Correct 239 ms 63500 KB Output is correct
12 Correct 202 ms 61660 KB Output is correct
13 Correct 187 ms 62484 KB Output is correct
14 Correct 176 ms 62492 KB Output is correct
15 Correct 188 ms 62556 KB Output is correct
16 Correct 194 ms 62252 KB Output is correct
17 Correct 187 ms 62408 KB Output is correct
18 Correct 197 ms 62484 KB Output is correct
19 Correct 181 ms 62428 KB Output is correct
20 Correct 187 ms 62492 KB Output is correct
21 Correct 186 ms 62228 KB Output is correct
22 Correct 185 ms 62336 KB Output is correct
23 Correct 179 ms 62172 KB Output is correct
24 Correct 186 ms 62128 KB Output is correct
25 Correct 187 ms 62072 KB Output is correct
26 Correct 168 ms 62088 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 924 ms 125068 KB Output is correct
2 Correct 896 ms 123360 KB Output is correct
3 Correct 821 ms 120328 KB Output is correct
4 Correct 874 ms 124416 KB Output is correct
5 Correct 879 ms 124108 KB Output is correct
6 Correct 519 ms 100048 KB Output is correct
7 Correct 611 ms 100404 KB Output is correct
8 Correct 561 ms 100576 KB Output is correct
9 Correct 554 ms 100672 KB Output is correct
10 Correct 580 ms 100680 KB Output is correct
11 Correct 566 ms 100708 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 48328 KB Output is correct
2 Correct 29 ms 48476 KB Output is correct
3 Correct 30 ms 48852 KB Output is correct
4 Correct 29 ms 48188 KB Output is correct
5 Correct 28 ms 48252 KB Output is correct
6 Correct 26 ms 48208 KB Output is correct
7 Correct 26 ms 48208 KB Output is correct
8 Correct 252 ms 62348 KB Output is correct
9 Correct 222 ms 62260 KB Output is correct
10 Correct 231 ms 62836 KB Output is correct
11 Correct 239 ms 63500 KB Output is correct
12 Correct 202 ms 61660 KB Output is correct
13 Correct 187 ms 62484 KB Output is correct
14 Correct 176 ms 62492 KB Output is correct
15 Correct 188 ms 62556 KB Output is correct
16 Correct 194 ms 62252 KB Output is correct
17 Correct 187 ms 62408 KB Output is correct
18 Correct 197 ms 62484 KB Output is correct
19 Correct 181 ms 62428 KB Output is correct
20 Correct 187 ms 62492 KB Output is correct
21 Correct 186 ms 62228 KB Output is correct
22 Correct 185 ms 62336 KB Output is correct
23 Correct 179 ms 62172 KB Output is correct
24 Correct 186 ms 62128 KB Output is correct
25 Correct 187 ms 62072 KB Output is correct
26 Correct 168 ms 62088 KB Output is correct
27 Correct 924 ms 125068 KB Output is correct
28 Correct 896 ms 123360 KB Output is correct
29 Correct 821 ms 120328 KB Output is correct
30 Correct 874 ms 124416 KB Output is correct
31 Correct 879 ms 124108 KB Output is correct
32 Correct 519 ms 100048 KB Output is correct
33 Correct 611 ms 100404 KB Output is correct
34 Correct 561 ms 100576 KB Output is correct
35 Correct 554 ms 100672 KB Output is correct
36 Correct 580 ms 100680 KB Output is correct
37 Correct 566 ms 100708 KB Output is correct
38 Correct 2517 ms 190904 KB Output is correct
39 Correct 2407 ms 209352 KB Output is correct
40 Correct 1928 ms 171008 KB Output is correct
41 Correct 1608 ms 207912 KB Output is correct
42 Correct 509 ms 98916 KB Output is correct
43 Correct 538 ms 101280 KB Output is correct
44 Correct 883 ms 141052 KB Output is correct
45 Correct 874 ms 141568 KB Output is correct
46 Correct 873 ms 142444 KB Output is correct
47 Correct 547 ms 102436 KB Output is correct
48 Correct 571 ms 102344 KB Output is correct
49 Correct 973 ms 142772 KB Output is correct
50 Correct 922 ms 142576 KB Output is correct
51 Correct 882 ms 142880 KB Output is correct
52 Correct 725 ms 126496 KB Output is correct
53 Correct 924 ms 160060 KB Output is correct
54 Correct 1068 ms 186236 KB Output is correct
55 Correct 845 ms 156528 KB Output is correct