Submission #1161794

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161794		mychecksedad	Gift Exchange (JOI24_ho_t4)	C++20	100 / 100	1546 ms	109288 KiB

Main

/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 4e6+100, M = 2e6+10, K = 52, MX = 30;

int RRR[N];
struct Fenwick{
  int n, tot, roll_size;
  vector<int> t, op;
  Fenwick(int _n){
    n = _n;
    tot = 0;
    roll_size = 0;
    t.resize(n+1, 0);
  }
  void add(int v, int x){
    if(x == 1) RRR[roll_size++] = v;
    ++tot;
    while(v <= n){
      t[v]+=x;
      v += (v&-v);
    }
  }
  int get(int v){
    int res = 0;
    while(v > 0){
      res += t[v];
      v -= (v&-v);
    }
    return res;
  }
  void roll(){
    for(int i = 0; i < roll_size; ++i) add(RRR[i], -1);
    roll_size = 0;
    tot = 0;
  }
} fw(500005);
 

int n, q, pos[N], T[N], TT[N], ans[N], QQ[N];
array<int, 2> a[N], bad[N];
vector<array<int, 2>> S[M];
void buildmax(){for(int j = 0; j <= 8*n; ++j) T[j] = 0;}
void buildmin(){for(int j = 0; j <= 8*n; ++j) TT[j] = n + 1;}
int getmax(int l, int r, int ql, int qr, int k){
  if(ql > r || l > qr) return 0;
  if(ql <= l && r <= qr) return T[k];
  int m = l+r>>1;
  return max(getmax(l, m, ql, qr, k<<1), getmax(m+1, r, ql, qr, k<<1|1));
}
int getmin(int l, int r, int ql, int qr, int k){
  if(ql > r || l > qr) return n + 1;
  if(ql <= l && r <= qr) return TT[k];
  int m = l+r>>1;
  return min(getmin(l, m, ql, qr, k<<1), getmin(m+1, r, ql, qr, k<<1|1));
}
void updmin(int l, int r, int p, int k, int val){
  if(l == r){
    TT[k] = val;
    return;
  }
  int m = l+r>>1;
  if(p <= m) updmin(l, m, p, k<<1, val);
  else updmin(m+1, r, p, k<<1|1, val);
  TT[k] = min(TT[k<<1], TT[k<<1|1]);
}
void updmax(int l, int r, int p, int k, int val){
  if(l == r){
    T[k] = val;
    return;
  }
  int m = l+r>>1;
  if(p <= m) updmax(l, m, p, k<<1, val);
  else updmax(m+1, r, p, k<<1|1, val);
  T[k] = max(T[k<<1], T[k<<1|1]);
}

int getmax2(int l, int r, int p, int k){
  if(l == r) return T[k];
  int m = l+r>>1;
  if(p <= m) return max(T[k], getmax2(l, m, p, k<<1));
  return max(T[k], getmax2(m+1, r, p, k<<1|1));
}
int getmin2(int l, int r, int p, int k){
  if(l == r) return TT[k];
  int m = l+r>>1;
  if(p <= m) return min(TT[k], getmin2(l, m, p, k<<1));
  return min(TT[k], getmin2(m+1, r, p, k<<1|1));
}
void updmin2(int l, int r, int ql, int qr, int k, int val){
  if(ql>r||l>qr) return;
  if(ql <= l && r <= qr){
    TT[k] = min(TT[k], val);
    return;
  }
  int m = l+r>>1;
  updmin2(l, m, ql, qr, k<<1, val);
  updmin2(m+1, r, ql, qr, k<<1|1, val);
}
void updmax2(int l, int r, int ql, int qr, int k, int val){
  if(ql>r||l>qr) return;
  if(ql <= l && r <= qr){
    T[k] = max(T[k], val);
    return;
  }
  int m = l+r>>1;
  updmax2(l, m, ql, qr, k<<1, val);
  updmax2(m+1, r, ql, qr, k<<1|1, val);
}

void add(int l, int r, int p, int k, int L){
  QQ[k] = min(QQ[k], L);
  if(l == r){
    return;
  }
  int m = l+r>>1;
  if(p <= m) add(l, m, p, k<<1, L);
  else add(m+1, r, p, k<<1|1, L);
}

int get(int l, int r, int ql, int qr, int k){
  if(ql > r || l > qr) return MOD;
  if(ql <= l && r <= qr) return QQ[k];
  int m = l+r>>1;
  return min(get(l, m, ql, qr, k<<1), get(m+1, r, ql, qr, k<<1|1));
}

void solve(){
  cin>> n;
  for(int i = 1; i <= n; ++i){
    cin >> a[i][0];
  }
  for(int i = 1; i <= n; ++i){
    cin >> a[i][1];
  }
  {
    buildmax();
    for(int i = 1; i <= n; ++i){
      int L = 1;
      L = getmax(1, n*2, a[i][1], a[i][0], 1) + 1;
      bad[i][0] = L;
      updmax(1, n*2, a[i][0], 1, i);
    }
    buildmin();
    for(int i = n; i >= 1; --i){
      int R = n;
      R = getmin(1, n*2, a[i][1], a[i][0], 1) - 1;
      bad[i][1] = R;
      updmin(1, n*2, a[i][0], 1, i);
    }
  }
  {
    buildmax();
    for(int i = 1; i <= n; ++i){
      int L = 1;
      L = getmax2(1, n*2, a[i][0], 1) + 1;
      bad[i][0] = max(bad[i][0], L);
      updmax2(1, n*2, a[i][1], a[i][0], 1, i);
    }
    buildmin();
    for(int i = n; i >= 1; --i){
      int R = n;
      R = getmin2(1, n*2, a[i][0], 1) - 1;
      bad[i][1] = min(bad[i][1], R);
      updmin2(1, n*2, a[i][1], a[i][0], 1, i);
    }
  }

  vector<array<int, 3>> badd;
  for(int i = 1; i <= n; ++i){
    badd.pb({bad[i][1], bad[i][0], i});
    // cout << bad[i][1] << ' ' << bad[i][0] << '\n';
  }
  vector<array<int, 3>> Q;
  cin >> q;
  vector<int> ans(q+1);
  for(int i = 1; i <= q; ++i){
    int l, r; cin >> l >> r;
    ans[i] = 1;
    Q.pb({r, l, i});
  }
  sort(all(badd));
  sort(all(Q));
  reverse(all(Q));
  for(int j = 0 ;j < 4*n; ++j) QQ[j] = MOD;
  for(auto [r, l, idx]: Q){
    while(badd.size() && badd.back()[0] >= r){
      add(1, n, badd.back()[2], 1, badd.back()[1]);
      badd.pop_back();
    }
    // cout << get(1, n, l, r, 1) << "31\n";
    ans[idx] = get(1, n, l, r, 1) > l;
  }

  for(int i = 1; i <= q; ++i){
    cout << (ans[i]?"Yes\n":"No\n");
  }
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\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: 12 / 12