제출 #1248850

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1248850		meisgood	Gift Exchange (JOI24_ho_t4)	C++20	88 / 100	1460 ms	234296 KiB

Main

#include <bits/stdc++.h>
using namespace std ;
#define int long long
int A[500003] ;
int B[500003] ;
struct SEGT {
  int seg[4000003] ;
  int lzt[4000003] ;
  int type ;
  int get(int a,int b){
    if (type==0) return min(a,b) ;
    else return max(a,b) ;
  }
  void build(int ty){
    type=ty ;
    for (int i = 0 ; i < 4000003 ; i ++) seg[i]=lzt[i]=(type==0?INT_MAX:0) ;
  }
  void push_down(int id){
    lzt[id*2]=get(lzt[id*2],lzt[id]) ;
    lzt[id*2+1]=get(lzt[id*2+1],lzt[id]) ;
    seg[id*2]=get(seg[id*2],lzt[id]) ;
    seg[id*2+1]=get(seg[id*2+1],lzt[id]) ;
    lzt[id]=(type==0?INT_MAX:0) ;
  }
  void upd(int id,int l,int r,int ql,int qr,int x){
    if (ql<=l&&r<=qr) seg[id]=lzt[id]=get(seg[id],x) ;
    else if (l>qr||r<ql) ;
    else {
      int md=(l+r)/2 ;
      push_down(id) ;
      upd(id*2,l,md,ql,qr,x) ;
      upd(id*2+1,md+1,r,ql,qr,x) ;
      seg[id]=get(seg[id*2],seg[id*2+1]) ;
    }
  }
  int qq(int id,int l,int r,int ql,int qr){
    if (ql<=l&&r<=qr) return seg[id] ;
    else if (l>qr||r<ql) return (type==0?INT_MAX:0) ;
    else {
      int md=(l+r)/2 ;
      push_down(id) ;
      return get(qq(id*2,l,md,ql,qr),qq(id*2+1,md+1,r,ql,qr)) ;
    }
  }
} ;
int prv[500003],nxt[500003] ;
vector <int> ndel[500003] ;
signed main(){
  int N,i,j ;
  cin >> N ;
  for (i = 1 ; i <= N ; i ++) cin >> B[i],B[i]-- ;
  for (i = 1 ; i <= N ; i ++) cin >> A[i] ;
  SEGT mx,mn ;
  mx.build(1) ;
  mn.build(0) ;
  SEGT mnnd ;
  mnnd.build(1) ;
  for (i = 1 ; i <= N ; i ++){
    prv[i]=mx.qq(1,1,2*N,A[i],B[i]) ;
    ndel[prv[i]].push_back(i) ;
    mx.upd(1,1,2*N,A[i],B[i],i) ;
  }
  for (i = N ; i >= 1 ; i --){
    nxt[i]=mn.qq(1,1,2*N,A[i],B[i]) ;
    mn.upd(1,1,2*N,A[i],B[i],i) ;
  }
  int Q ;
  cin >> Q ;
  int ans[200003] ;
  vector <pair<int,int>> qs[200003] ;
  for (i = 1 ; i <= Q ; i ++){
    int a,b ;
    cin >> a >> b ;
    qs[a].push_back({b,i}) ;
  }
  for (auto x : ndel[0]){
    mnnd.upd(1,1,2*N,x,x,nxt[x]) ;
    // cout << x << " " << nxt[x] << endl ;
  }
  for (i = 1 ; i <= N ; i ++){
    for (auto [a,id] : qs[i]){
      if (mnnd.qq(1,1,2*N,i,a)>a) ans[id]=0 ;
      else ans[id]=1 ;
    }
    for (auto x : ndel[i]){
      mnnd.upd(1,1,2*N,x,x,nxt[x]) ;
      // cout << i << " " << x << " " << nxt[x] << endl ;
    }
  }
  for (i = 1 ; i <= Q ; i ++){
    if (ans[i]) cout << "Yes\n" ;
    else cout << "No\n" ;
  }
	return 0 ;
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 31 / 31
• Subtask 5: 8 / 8
• Subtask 6: 12 / 12
• Subtask 7: 18 / 18
• Subtask 8: 0 / 12