Submission #718014

#	Time	Username	Problem	Language	Result	Execution time	Memory
718014		MohammadAghil	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	655 ms	66428 KiB

long_mansion

      #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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 75 / 75