oj.uz

Submission #1097386

# Submission time Handle Problem Language Result Execution time Memory
1097386 2024-10-07T07:10:18 Z 8pete8 Long Mansion (JOI17_long_mansion) C++17
100 / 100
 681 ms 90452 KB 
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define int long long
#define double long double
using namespace std;
const int mod=998244353,mxn=5e5+5,inf=1e18,minf=-1e18,lg=62;
//#undef int
int n,k,m,q;
void setIO(string name){		
	ios_base::sync_with_stdio(0); cin.tie(0);		
	freopen((name+".in").c_str(),"r",stdin);		
	freopen((name+".out").c_str(),"w",stdout);	
}
int door[mxn+10],where[mxn+10],wheredoor[mxn+10];
vector<int>add[mxn+10],have[mxn+10];
pii ans[mxn+10];
int on[mxn+10];
int32_t main(){
    fastio
	int n;cin>>n;
	for(int i=1;i<=n-1;i++)cin>>door[i];
    for(int i=1;i<=n;i++){
        int a;cin>>a;
        for(int j=0;j<a;j++){
            int x;cin>>x;
            have[i].pb(x);
        }
    }
    set<int>st;
    for(int i=1;i<=n-1;i++){
        for(auto j:have[i]){
            if(on[wheredoor[j]])st.erase(st.find(wheredoor[j])),on[wheredoor[j]]=0;
            where[j]=i;
        }
        if(where[door[i]]){
            auto it=st.lb(where[door[i]]);
            if(it!=st.end())add[(*it)+1].pb(i);
        }
        else add[1].pb(i);
        st.insert(i);
        on[i]=1;
        if(on[wheredoor[door[i]]])st.erase(st.find(wheredoor[door[i]]));
        wheredoor[door[i]]=i;
        
    }
    priority_queue<int,vector<int>,greater<int>>r;
    r.push(n);
    for(int i=1;i<=n;i++){
        for(auto j:add[i])r.push(j);
        while(!r.empty()&&r.top()<i)r.pop();
        ans[i].s=r.top();
        add[i].clear();
        on[i]=0;
        wheredoor[i]=0;
        where[i]=0;
    }
    st.clear();
    for(int i=n-1;i>=1;i--){
        for(auto j:have[i+1]){
            if(on[wheredoor[j]])st.erase(st.find(wheredoor[j])),on[wheredoor[j]]=0;
            where[j]=i;
        }
        if(where[door[i]]){
            auto it=st.upper_bound(where[door[i]]);
            if(it!=st.begin())add[(*prev(it))].pb(i+1);
        }
        else add[n].pb(i+1);
        st.insert(i);
        on[i]=1;
        if(on[wheredoor[door[i]]])st.erase(st.find(wheredoor[door[i]]));
        wheredoor[door[i]]=i;
    }
    priority_queue<int>l;
    l.push(1);
    for(int i=n;i>=1;i--){
        for(auto j:add[i])l.push(j);
        while(!l.empty()&&l.top()>i)l.pop();
        ans[i].f=l.top();
    }
	int q;cin>>q;
	while(q--){
		int a,b;cin>>a>>b;
		if(b>=ans[a].f&&b<=ans[a].s)cout<<"YES\n";
		else cout<<"NO\n";
	}
}
/*
 
lets say we are at point x
if there exist a "color" of key where
door i seperates room i,i+1
the last appearance of door before x and first after x (l,r)
l<x and x<=r
and the last appearance of room with that color of key before x and first after x (l2,r2)
if l2 <= l < r < r2
then no matter how we move we cant go outside the range (l+1,r)
 
so door[l] and doo[r] doesnt have to be the same type
 
for each possible r we can find the least l where the condition is met
then every thing in range (l,r) cant move outside r
then do the same for l
 
*/

Compilation message

long_mansion.cpp:32:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   32 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
long_mansion.cpp:39:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   39 | void setIO(string name){
      |                       ^
long_mansion.cpp:48:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   48 | int32_t main(){
      |              ^
long_mansion.cpp: In function 'void setIO(std::string)':
long_mansion.cpp:41:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
long_mansion.cpp:42:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24152 KB Output is correct
2 Correct 14 ms 24292 KB Output is correct
3 Correct 13 ms 24408 KB Output is correct
4 Correct 11 ms 24212 KB Output is correct
5 Correct 12 ms 24156 KB Output is correct
6 Correct 12 ms 24112 KB Output is correct
7 Correct 13 ms 24156 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24152 KB Output is correct
2 Correct 14 ms 24292 KB Output is correct
3 Correct 13 ms 24408 KB Output is correct
4 Correct 11 ms 24212 KB Output is correct
5 Correct 12 ms 24156 KB Output is correct
6 Correct 12 ms 24112 KB Output is correct
7 Correct 13 ms 24156 KB Output is correct
8 Correct 69 ms 29864 KB Output is correct
9 Correct 70 ms 30032 KB Output is correct
10 Correct 73 ms 30480 KB Output is correct
11 Correct 72 ms 30800 KB Output is correct
12 Correct 72 ms 29584 KB Output is correct
13 Correct 68 ms 30224 KB Output is correct
14 Correct 70 ms 30204 KB Output is correct
15 Correct 67 ms 29980 KB Output is correct
16 Correct 64 ms 29780 KB Output is correct
17 Correct 72 ms 30032 KB Output is correct
18 Correct 66 ms 30212 KB Output is correct
19 Correct 62 ms 30096 KB Output is correct
20 Correct 62 ms 30036 KB Output is correct
21 Correct 59 ms 29864 KB Output is correct
22 Correct 61 ms 29872 KB Output is correct
23 Correct 67 ms 29868 KB Output is correct
24 Correct 73 ms 30036 KB Output is correct
25 Correct 66 ms 30040 KB Output is correct
26 Correct 68 ms 30036 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 45904 KB Output is correct
2 Correct 144 ms 45304 KB Output is correct
3 Correct 130 ms 44368 KB Output is correct
4 Correct 150 ms 45748 KB Output is correct
5 Correct 147 ms 45560 KB Output is correct
6 Correct 107 ms 40788 KB Output is correct
7 Correct 105 ms 39760 KB Output is correct
8 Correct 105 ms 39760 KB Output is correct
9 Correct 109 ms 39872 KB Output is correct
10 Correct 98 ms 39760 KB Output is correct
11 Correct 97 ms 39760 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24152 KB Output is correct
2 Correct 14 ms 24292 KB Output is correct
3 Correct 13 ms 24408 KB Output is correct
4 Correct 11 ms 24212 KB Output is correct
5 Correct 12 ms 24156 KB Output is correct
6 Correct 12 ms 24112 KB Output is correct
7 Correct 13 ms 24156 KB Output is correct
8 Correct 69 ms 29864 KB Output is correct
9 Correct 70 ms 30032 KB Output is correct
10 Correct 73 ms 30480 KB Output is correct
11 Correct 72 ms 30800 KB Output is correct
12 Correct 72 ms 29584 KB Output is correct
13 Correct 68 ms 30224 KB Output is correct
14 Correct 70 ms 30204 KB Output is correct
15 Correct 67 ms 29980 KB Output is correct
16 Correct 64 ms 29780 KB Output is correct
17 Correct 72 ms 30032 KB Output is correct
18 Correct 66 ms 30212 KB Output is correct
19 Correct 62 ms 30096 KB Output is correct
20 Correct 62 ms 30036 KB Output is correct
21 Correct 59 ms 29864 KB Output is correct
22 Correct 61 ms 29872 KB Output is correct
23 Correct 67 ms 29868 KB Output is correct
24 Correct 73 ms 30036 KB Output is correct
25 Correct 66 ms 30040 KB Output is correct
26 Correct 68 ms 30036 KB Output is correct
27 Correct 135 ms 45904 KB Output is correct
28 Correct 144 ms 45304 KB Output is correct
29 Correct 130 ms 44368 KB Output is correct
30 Correct 150 ms 45748 KB Output is correct
31 Correct 147 ms 45560 KB Output is correct
32 Correct 107 ms 40788 KB Output is correct
33 Correct 105 ms 39760 KB Output is correct
34 Correct 105 ms 39760 KB Output is correct
35 Correct 109 ms 39872 KB Output is correct
36 Correct 98 ms 39760 KB Output is correct
37 Correct 97 ms 39760 KB Output is correct
38 Correct 681 ms 80684 KB Output is correct
39 Correct 605 ms 90452 KB Output is correct
40 Correct 400 ms 68948 KB Output is correct
41 Correct 237 ms 80848 KB Output is correct
42 Correct 129 ms 42068 KB Output is correct
43 Correct 137 ms 41300 KB Output is correct
44 Correct 184 ms 51792 KB Output is correct
45 Correct 185 ms 51852 KB Output is correct
46 Correct 171 ms 51660 KB Output is correct
47 Correct 103 ms 41040 KB Output is correct
48 Correct 107 ms 40788 KB Output is correct
49 Correct 142 ms 51280 KB Output is correct
50 Correct 144 ms 51392 KB Output is correct
51 Correct 144 ms 51764 KB Output is correct
52 Correct 218 ms 59200 KB Output is correct
53 Correct 314 ms 72652 KB Output is correct
54 Correct 402 ms 87520 KB Output is correct
55 Correct 378 ms 75972 KB Output is correct