제출 #1248821

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

Main

#include <bits/stdc++.h>
using namespace std ;
#define int long long
const int bl=sqrt(100000) ;
bool comp(tuple<int,int,int>a,tuple<int,int,int>b){
  if (get<0>(a)/bl==get<0>(b)/bl){
    if ((get<0>(a)/bl)%2) return get<1>(a)<get<1>(b) ;
    else return get<1>(a)>get<1>(b) ;
  }
  else return get<0>(a)/bl<get<0>(b)/bl ;
}
int A[100003] ;
int B[100003] ;
struct SEGT {
  int seg[800003] ;
  int lzt[800003] ;
  void build(){
    for (int i = 0 ; i < 800003 ; i ++) seg[i]=lzt[i]=0 ;
  }
  void push_down(int id){
    lzt[id*2]+=lzt[id] ;
    lzt[id*2+1]+=lzt[id] ;
    seg[id*2]+=lzt[id] ;
    seg[id*2+1]+=lzt[id] ;
    lzt[id]=0 ;
  }
  void upd(int id,int l,int r,int ql,int qr,int x){
    if (ql<=l&&r<=qr) seg[id]+=x,lzt[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]=min(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 INT_MAX ;
    else {
      int md=(l+r)/2 ;
      push_down(id) ;
      return min(qq(id*2,l,md,ql,qr),qq(id*2+1,md+1,r,ql,qr)) ;
    }
  }
} ;
signed main(){
  int N,i,j ;
  cin >> N ;
  for (i = 1 ; i <= N ; i ++) cin >> A[i] ;
  for (i = 1 ; i <= N ; i ++) cin >> B[i] ;
  int ans[100003] ;
  multiset <int> ms ;
  multiset <int> ms2 ;
  int l=1,r=1 ;
  int Q ;
  cin >> Q ;
  vector <tuple<int,int,int>> qs ;
  for (i = 1 ; i <= Q ; i ++){
    int a,b ;
    cin >> a >> b ;
    qs.push_back({a,b,i}) ;
  }
  sort(qs.begin(),qs.end(),comp) ;
  SEGT sgt ;
  sgt.build() ;
  for (auto [a,b,x] : qs){
    // cout << a << " " << b << " " << x << endl ;
    while (r<=b){
      sgt.upd(1,1,N*2,B[r],A[r]-1,1) ;
      ms.insert(A[r]) ;
      ms2.insert(B[r]) ;
      r++ ;
    }
    while (l>a){
      l-- ;
      sgt.upd(1,1,N*2,B[l],A[l]-1,1) ;
      ms.insert(A[l]) ;
      ms2.insert(B[l]) ;
    }
    while (l<a){
      sgt.upd(1,1,N*2,B[l],A[l]-1,-1) ;
      ms.erase(ms.find(A[l])) ;
      ms2.erase(ms2.find(B[l])) ;
      l++ ;
    }
    while (r>b+1){
      r-- ;
      sgt.upd(1,1,N*2,B[r],A[r]-1,-1) ;
      ms.erase(ms.find(A[r])) ;
      ms2.erase(ms2.find(B[r])) ;
    }
    // cout << *ms2.begin() << " " << *--ms.end() << endl ;
    ans[x]=(sgt.qq(1,1,N*2,*ms2.begin(),*--ms.end()-1)!=0) ;
  }
  for (i = 1 ; i <= Q ; i ++){
    if (ans[i]) cout << "Yes\n" ;
    else cout << "No\n" ;
  }
	return 0 ;
}

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