oj.uz

Submission #718014

# Submission time Handle Problem Language Result Execution time Memory
718014 2023-04-03T06:59:38 Z MohammadAghil Long Mansion (JOI17_long_mansion) C++17
100 / 100
 655 ms 66428 KB 
      #include <bits/stdc++.h>
//   #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
 using namespace std;
  typedef long long ll;
   typedef pair<int, int> pp;
     #define per(i,r,l) for(int i = (r); i >= (l); i--)
       #define rep(i,l,r) for(int i = (l); i < (r); i++)
          #define all(x) begin(x), end(x)
             #define sz(x) (int)(x).size()
                 #define pb push_back
                     #define ss second
                          #define ff first
                                  void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
void IOS(){
     cin.tie(0) -> sync_with_stdio(0);
     #ifndef ONLINE_JUDGE
          #define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
          // freopen("inp.txt", "r", stdin);
          // freopen("out.txt", "w", stdout);
     #else
          #define er(args ...) 0
     #endif
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 998244353, maxn = 5e5 + 5, lg = 22, inf = ll(1e9) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll,md);return k*k%md*(b&1ll?a:1)%md;}

int c[maxn];
vector<int> str[maxn];
int lx[maxn], rx[maxn];
int nxt[maxn], prv[maxn];
int seg[maxn<<2];

void build(int x = 1, int lx = 0, int rx = maxn){
     if(lx + 1 == rx){
          seg[x] = nxt[lx];
          return;
     }
     int mid = (lx + rx)>>1;
     build(x<<1, lx, mid);
     build(x<<1|1, mid, rx);
     seg[x] = max(seg[x<<1], seg[x<<1|1]);
}

int get(int l, int r, int x = 1, int lx = 0, int rx = maxn){
     if(l <= lx && r >= rx) return seg[x];
     int mid = (lx + rx)>>1;
     int res = 0;
     if(l < mid) res = max(res, get(l, r, x<<1, lx, mid));
     if(mid < r) res = max(res, get(l, r, x<<1|1, mid, rx));
     return res; 
}

int gett(int mx, int r, int x = 1, int lx = 0, int rx = maxn){
     if(r <= lx) return maxn;
     int mid = (lx + rx)>>1;
     if(rx <= r){
          if(seg[x] <= mx) return maxn;
          if(lx + 1 == rx) return lx;
          if(seg[x<<1|1] > mx) return gett(mx, r, x<<1|1, mid, rx);
          return gett(mx, r, x<<1, lx, mid);
     }
     int res = gett(mx, r, x<<1|1, mid, rx);
     if(res - maxn) return res;
     return gett(mx, r, x<<1, lx, mid);
}

int main(){ IOS();
     int n; cin >> n;
     rep(i,0,n-1){
          cin >> c[i];
     }
     rep(i,0,n){
          int a; cin >> a;
          rep(j,0,a){
               int k; cin >> k;
               str[i].pb(k);
          }
     }
     map<int, int> mp;
     rep(i,0,n-1){
          for(int x: str[i]) mp[x] = i;
          prv[i] = mp.count(c[i])? mp[c[i]]: -1;
     }
     mp.clear();
     per(i,n-2,0){
          for(int x: str[i + 1]) mp[x] = i + 1;
          nxt[i] = mp.count(c[i])? mp[c[i]]: n;
     }
     build();
     vector<int> stk;
     per(i,n-1,0){
          while(sz(stk)){
               int nx = stk.back();
               int f = prv[nx-1];
               if(f == -1) break;
               bool ok = false;
               if(f >= i) ok = true;
               else{
                    if(get(f, i) < nx) ok = true;
               }
               if(ok) stk.pop_back();
               else break;
          }
          if(sz(stk)){
               rx[i] = stk.back() - 1;
          } else{
               rx[i] = n-1;
          }
          lx[i] = gett(rx[i], i) + 1;
          if(lx[i] == maxn + 1) lx[i] = 0;
          stk.pb(i);
     }
     int q; cin >> q;
     while(q--){
          int x, y; cin >> x >> y; x--, y--;
          cout << (y >= lx[x] && y <= rx[x]? "YES\n": "NO\n");
     }
     return 0-0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16340 KB Output is correct
2 Correct 14 ms 16452 KB Output is correct
3 Correct 16 ms 16548 KB Output is correct
4 Correct 17 ms 16456 KB Output is correct
5 Correct 16 ms 16296 KB Output is correct
6 Correct 14 ms 16468 KB Output is correct
7 Correct 14 ms 16468 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16340 KB Output is correct
2 Correct 14 ms 16452 KB Output is correct
3 Correct 16 ms 16548 KB Output is correct
4 Correct 17 ms 16456 KB Output is correct
5 Correct 16 ms 16296 KB Output is correct
6 Correct 14 ms 16468 KB Output is correct
7 Correct 14 ms 16468 KB Output is correct
8 Correct 98 ms 22208 KB Output is correct
9 Correct 95 ms 22152 KB Output is correct
10 Correct 98 ms 22548 KB Output is correct
11 Correct 101 ms 22912 KB Output is correct
12 Correct 93 ms 21836 KB Output is correct
13 Correct 96 ms 22392 KB Output is correct
14 Correct 92 ms 22460 KB Output is correct
15 Correct 100 ms 22320 KB Output is correct
16 Correct 91 ms 22140 KB Output is correct
17 Correct 115 ms 22304 KB Output is correct
18 Correct 96 ms 22392 KB Output is correct
19 Correct 94 ms 22420 KB Output is correct
20 Correct 123 ms 22328 KB Output is correct
21 Correct 91 ms 22200 KB Output is correct
22 Correct 100 ms 22324 KB Output is correct
23 Correct 112 ms 22228 KB Output is correct
24 Correct 93 ms 22252 KB Output is correct
25 Correct 93 ms 22220 KB Output is correct
26 Correct 95 ms 22260 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 30840 KB Output is correct
2 Correct 228 ms 30772 KB Output is correct
3 Correct 204 ms 30512 KB Output is correct
4 Correct 216 ms 30860 KB Output is correct
5 Correct 211 ms 30796 KB Output is correct
6 Correct 157 ms 29552 KB Output is correct
7 Correct 170 ms 29324 KB Output is correct
8 Correct 152 ms 29288 KB Output is correct
9 Correct 166 ms 29372 KB Output is correct
10 Correct 149 ms 29276 KB Output is correct
11 Correct 151 ms 29228 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16340 KB Output is correct
2 Correct 14 ms 16452 KB Output is correct
3 Correct 16 ms 16548 KB Output is correct
4 Correct 17 ms 16456 KB Output is correct
5 Correct 16 ms 16296 KB Output is correct
6 Correct 14 ms 16468 KB Output is correct
7 Correct 14 ms 16468 KB Output is correct
8 Correct 98 ms 22208 KB Output is correct
9 Correct 95 ms 22152 KB Output is correct
10 Correct 98 ms 22548 KB Output is correct
11 Correct 101 ms 22912 KB Output is correct
12 Correct 93 ms 21836 KB Output is correct
13 Correct 96 ms 22392 KB Output is correct
14 Correct 92 ms 22460 KB Output is correct
15 Correct 100 ms 22320 KB Output is correct
16 Correct 91 ms 22140 KB Output is correct
17 Correct 115 ms 22304 KB Output is correct
18 Correct 96 ms 22392 KB Output is correct
19 Correct 94 ms 22420 KB Output is correct
20 Correct 123 ms 22328 KB Output is correct
21 Correct 91 ms 22200 KB Output is correct
22 Correct 100 ms 22324 KB Output is correct
23 Correct 112 ms 22228 KB Output is correct
24 Correct 93 ms 22252 KB Output is correct
25 Correct 93 ms 22220 KB Output is correct
26 Correct 95 ms 22260 KB Output is correct
27 Correct 210 ms 30840 KB Output is correct
28 Correct 228 ms 30772 KB Output is correct
29 Correct 204 ms 30512 KB Output is correct
30 Correct 216 ms 30860 KB Output is correct
31 Correct 211 ms 30796 KB Output is correct
32 Correct 157 ms 29552 KB Output is correct
33 Correct 170 ms 29324 KB Output is correct
34 Correct 152 ms 29288 KB Output is correct
35 Correct 166 ms 29372 KB Output is correct
36 Correct 149 ms 29276 KB Output is correct
37 Correct 151 ms 29228 KB Output is correct
38 Correct 629 ms 49016 KB Output is correct
39 Correct 568 ms 53952 KB Output is correct
40 Correct 472 ms 43288 KB Output is correct
41 Correct 352 ms 52544 KB Output is correct
42 Correct 240 ms 32564 KB Output is correct
43 Correct 258 ms 31380 KB Output is correct
44 Correct 441 ms 41200 KB Output is correct
45 Correct 453 ms 41852 KB Output is correct
46 Correct 440 ms 42820 KB Output is correct
47 Correct 256 ms 32580 KB Output is correct
48 Correct 245 ms 30800 KB Output is correct
49 Correct 406 ms 39880 KB Output is correct
50 Correct 427 ms 41400 KB Output is correct
51 Correct 525 ms 43912 KB Output is correct
52 Correct 346 ms 46144 KB Output is correct
53 Correct 503 ms 55880 KB Output is correct
54 Correct 655 ms 66428 KB Output is correct
55 Correct 476 ms 56980 KB Output is correct