Submission #1162295

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162295		Zero_OP	Gift Exchange (JOI24_ho_t4)	C++20	100 / 100	1062 ms	123672 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define ROF(i, r, l) for(int i = (r) - 1; i >= (l); --i)

#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back
#define compact(v) v.erase(unique(all(v)), end(v))

#define dbg(x) "[" #x " = " << (x) << "]"

template<typename T>
bool minimize(T& a, const T& b){
      if(a > b) return a = b, true;
      return false;
}

template<typename T>
bool maximize(T& a, const T& b){
      if(a < b) return a = b, true;
      return false;
}

using ll = long long;
using db = double;
using ld = long double;
using ull = unsigned long long;

using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;

using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
using vc = vector<char>;
using vd = vector<db>;

using vpi = vector<pi>;
using vpl = vector<pl>;

void setIO(){
      ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
      freopen("task.inp", "r", stdin);
      freopen("task.out", "w", stdout);
#endif // LOCAL
}

const int inf = 1e9;

struct SegmentTreeMin{
      vi st, lazy;
      SegmentTreeMin(int n) : st(n << 2, inf), lazy(n << 2, inf) {}

      void apply(int id, int val){
            st[id] = min(st[id], val);
            lazy[id] = min(lazy[id], val);
      }

      void down(int id){
            if(lazy[id] != inf){
                  apply(id << 1, lazy[id]);
                  apply(id << 1 | 1, lazy[id]);
                  lazy[id] = inf;
            }
      }

      void update(int id, int l, int r, int u, int v, int val){
            if(u <= l && r <= v) apply(id, val);
            else{
                  int mid = l + r >> 1;
                  down(id);
                  if(u <= mid) update(id << 1, l, mid, u, v, val);
                  if(mid < v)  update(id << 1 | 1, mid + 1, r, u, v, val);
                  st[id] = min(st[id << 1], st[id << 1 | 1]);
            }
      }

      int query(int id, int l, int r, int u, int v){
            if(v < l || u > r) return inf;
            if(u <= l && r <= v) return st[id];
            int mid = l + r >> 1; down(id);
            return min(query(id << 1, l, mid, u, v), query(id << 1 | 1, mid + 1, r, u, v));
      }

      void debug(int id, int l, int r){
            if(l == r) cout << st[id] << ' ';
            else{
                  int mid = l + r >> 1;
                  down(id);
                  debug(id << 1, l, mid);
                  debug(id << 1 | 1, mid + 1, r);
            }
      }
};


struct SegmentTreeMax{
      vi st, lazy;
      SegmentTreeMax(int n) : st(n << 2, -inf), lazy(n << 2, -inf) {}

      void apply(int id, int val){
            st[id] = max(st[id], val);
            lazy[id] = max(lazy[id], val);
      }

      void down(int id){
            if(lazy[id] != -inf){
                  apply(id << 1, lazy[id]);
                  apply(id << 1 | 1, lazy[id]);
                  lazy[id] = -inf;
            }
      }

      void update(int id, int l, int r, int u, int v, int val){
            if(u <= l && r <= v) apply(id, val);
            else{
                  int mid = l + r >> 1;
                  down(id);
                  if(u <= mid) update(id << 1, l, mid, u, v, val);
                  if(mid < v)  update(id << 1 | 1, mid + 1, r, u, v, val);
                  st[id] = max(st[id << 1], st[id << 1 | 1]);
            }
      }

      int query(int id, int l, int r, int u, int v){
            if(v < l || u > r) return -inf;
            if(u <= l && r <= v) return st[id];
            int mid = l + r >> 1; down(id);
            return max(query(id << 1, l, mid, u, v), query(id << 1 | 1, mid + 1, r, u, v));
      }
};

struct SegmentTree{
      vi st;
      SegmentTree(int n) : st(n << 2, -inf) {}

      void update(int id, int l, int r, int pos, int val){
            if(l == r) st[id] = max(st[id], val);
            else{
                  int mid = l + r >> 1;
                  if(pos <= mid) update(id << 1, l, mid, pos, val);
                  else update(id << 1 | 1, mid + 1, r, pos, val);
                  st[id] = min(st[id << 1], st[id << 1 | 1]);
            }
      }

      int query(int id, int l, int r, int u, int v){
            if(v < l || u > r) return inf;
            if(u <= l && r <= v) return st[id];
            int mid = l + r >> 1;
            return min(query(id << 1, l, mid, u, v), query(id << 1 | 1, mid + 1, r, u, v));
      }

      void debug(int id, int l, int r){
            if(l == r) cout << st[id] << ' ';
            else{
                  int mid = l + r >> 1;
                  debug(id << 1, l, mid);
                  debug(id << 1 | 1, mid + 1, r);
            }
      }
};

int main(){
      setIO();

      int N; cin >> N;
      vi A(N), B(N);
      FOR(i, 0, N) cin >> A[i];
      FOR(i, 0, N) cin >> B[i];

      vi L(N), R(N);

      SegmentTreeMax Tmax(2 * N);
      FOR(i, 0, N){
            L[i] = Tmax.query(1, 1, 2 * N, B[i], A[i]);
            Tmax.update(1, 1, 2 * N, B[i], A[i], i);
      }

      SegmentTreeMin Tmin(2 * N);
      ROF(i, N, 0){
            R[i] = Tmin.query(1, 1, 2 * N, B[i], A[i]);
            Tmin.update(1, 1, 2 * N, B[i], A[i], i);
      }

//      FOR(i, 0, N) cout << L[i] << ' ' << i << "\n\n"[i == N-1]; cout << '\n';
//      FOR(i, 0, N) cout << i << ' ' << R[i] << "\n\n"[i == N-1];

      SegmentTree T(N);
      vector<vpi> sweeps(N);
      FOR(i, 0, N){
            T.update(1, 0, N-1, i, L[i]);
            if(R[i] != inf) sweeps[R[i]].eb(i, i);
      }

      int Q;
      cin >> Q;
      vector<vpi> queries(N);
      FOR(i, 0, Q){
            int l, r;
            cin >> l >> r;
            --l, --r;
            queries[r].eb(l, i);
      }

      vb ans(Q);
      FOR(i, 0, N){
            for(auto [pos, val] : sweeps[i]) {
//                  cout << pos << " : " << val << '\n';
                  T.update(1, 0, N-1, pos, val);
            }

//            T.debug(1, 0, N-1); cout << '\n';
            for(auto [j, id] : queries[i]){
                  int cur = T.query(1, 0, N-1, j, i);
//                  cout << dbg(j) << dbg(i) << dbg(id) << dbg(cur) << '\n';
                  ans[id] = cur >= j;
            }
      }

      FOR(i, 0, Q){
            cout << (ans[i] ? "Yes\n" : "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: 12 / 12