Submission #1244775

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244775		Geforgs	Gift Exchange (JOI24_ho_t4)	C++20	100 / 100	1936 ms	218292 KiB

Main

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <unordered_map>
#include <stack>
#include <bit>
#include <bitset>
#include <string>
#include <cstring>
#include <iterator>
#include <random>
#define ll long long
#define ld long double
#define inf (ll)(2*1e18)
#define sort(a) sort(a.begin(), a.end())
#define reverse(a) reverse(a.begin(), a.end())
#define pb push_back
#define endl "\n"
using namespace std;

template<typename A, typename Concatenate, typename PushT>
class lazySegmentTree{
    ll size;
    A neutralElement;
    vector<A> a;
    vector<A> p;
    Concatenate con;
    PushT Push;
public:
    lazySegmentTree(ll size, A neutralElement);
    lazySegmentTree(ll size, A neutralElement, vector<A>& values);
    void update(ll pos, A val);
    void update(ll l, ll r, A val);
    A get(ll l, ll r);
private:
    void build(ll id, ll l, ll r);
    void build(ll id, ll l, ll r, vector<A>& values);
    void update(ll id, ll l, ll r, ll pos, A val);
    void update(ll id, ll l, ll r, ll tl, ll tr, A val);
    A get(ll id, ll l, ll r, ll tl, ll tr);
    void push(ll id, ll l, ll r);
};

struct con1{
    ll operator()(const ll& a, const ll& b) const{
        return max(a, b);
    }
};

struct push1{
    ll operator()(const ll& a, const ll& b, ll len) const{
        return max(a, b);
    }
};

struct con2{
    ll operator()(const ll& a, const ll& b) const{
        return min(a, b);
    }
};

struct push2{
    ll operator()(const ll& a, const ll& b, ll len) const{
        return min(a, b);
    }
};

void solve(){
    ll n, q, i, j, l, r;
    cin>>n;
    vector<ll> a(n);
    vector<ll> b(n);
    vector<ll> left(n);
    vector<ll> right(n);
    for(i=0;i<n;++i){
        cin>>a[i];
        --a[i];
    }
    for(i=0;i<n;++i){
        cin>>b[i];
        --b[i];
    }
    lazySegmentTree<ll, con1, push1> leftTree(2*n, -inf);
    lazySegmentTree<ll, con2, push2> rightTree(2*n, inf);
    lazySegmentTree<ll, con2, push2> tree(n, inf);
    for(i=0;i<n;++i){
        left[i] = leftTree.get(b[i], a[i]);
        leftTree.update(b[i], a[i], i);
    }
    vector<vector<ll>> del(n);
    for(i=n-1;i>=0;--i){
        right[i] = rightTree.get(b[i], a[i]);
        rightTree.update(b[i], a[i], i);
        if(right[i] < n){
            del[right[i]].pb(i);
        }
    }
    cin>>q;
    vector<vector<pair<ll, ll>>> queries(n);
    vector<bool> answers(q, true);
    for(i=0;i<q;++i){
        cin>>l>>r;
        --l;
        --r;
        queries[r].pb({l, i});
    }
    for(i=0;i<n;++i){
        tree.update(i, left[i]);
        for(auto el: del[i]){
            tree.update(el, el);
        }
        for(auto el: queries[i]){
            if(el.first > tree.get(el.first, i)){
                answers[el.second] = false;
            }
        }
    }
    for(i=0;i<q;++i){
        if(answers[i]){
            cout<<"Yes"<<endl;
        }else{
            cout<<"No"<<endl;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    srand(time(nullptr));
    ll t=1;
//    cin>>t;
    for(;t>0;--t){
        solve();
    }
    return 0;
}

template<typename A, typename Concatenate, typename PushT>
lazySegmentTree<A, Concatenate, PushT>::lazySegmentTree(ll size, A neutralElement) {
    this->size = size;
    this->a.resize(4*this->size);
    this->p.resize(4*this->size, neutralElement);
    this->neutralElement = neutralElement;
    this->build(1, 0, size-1);
}

template<typename A, typename Concatenate, typename PushT>
lazySegmentTree<A, Concatenate, PushT>::lazySegmentTree(ll size, A neutralElement, vector<A>& values) {
    this->size = size;
    this->a.resize(4*this->size);
    this->p.resize(4*this->size, neutralElement);
    this->neutralElement = neutralElement;
    this->build(1, 0, size-1, values);
}

template<typename A, typename Concatenate, typename PushT>
void lazySegmentTree<A, Concatenate, PushT>::update(ll pos, A val) {
    this->update(1, 0, size-1, pos, val);
}

template<typename A, typename Concatenate, typename PushT>
void lazySegmentTree<A, Concatenate, PushT>::update(ll l, ll r, A val) {
    this->update(1, 0, size-1, l, r, val);
}

template<typename A, typename Concatenate, typename PushT>
A lazySegmentTree<A, Concatenate, PushT>::get(ll l, ll r){
    return this->get(1, 0, size-1, l, r);
}

template<typename A, typename Concatenate, typename PushT>
void lazySegmentTree<A, Concatenate, PushT>::build(ll id, ll l, ll r){
    if(l == r){
        a[id] = neutralElement;
        return;
    }
    ll m=(l+r)/2;
    build(2*id, l, m);
    build(2*id+1, m+1, r);
    a[id] = con(a[2*id], a[2*id + 1]);
}

template<typename A, typename Concatenate, typename PushT>
void lazySegmentTree<A, Concatenate, PushT>::build(ll id, ll l, ll r, vector<A>& values){
    if(l == r){
        a[id] = values[l];
        return;
    }
    ll m=(l+r)/2;
    build(2*id, l, m);
    build(2*id+1, m+1, r);
    a[id] = con(a[2*id], a[2*id + 1]);
}

template<typename A, typename Concatenate, typename PushT>
void lazySegmentTree<A, Concatenate, PushT>::update(ll id, ll l, ll r, ll pos, A val) {
    if(l == r){
        a[id] = val;
        return;
    }
    push(id, l, r);
    ll m = (l+r)/2;
    if(pos <= m) update(2*id, l, m, pos, val);
    else update(2*id+1, m+1, r, pos, val);
    a[id] = con(a[2*id], a[2*id + 1]);
}

template<typename A, typename Concatenate, typename PushT>
void lazySegmentTree<A, Concatenate, PushT>::update(ll id, ll l, ll r, ll tl, ll tr, A val) {
    if(r < tl or tr < l) return;
    if(tl <= l and r <= tr){
        a[id] = Push(a[id], val, r - l + 1);
        p[id] = con(p[id], val);
        return;
    }
    push(id, l, r);
    ll m=(l+r)/2;
    update(2*id, l, m, tl, tr, val);
    update(2*id+1, m+1, r, tl, tr, val);
    a[id] = con(a[2*id], a[2*id+1]);
}

template<typename A, typename Concatenate, typename PushT>
A lazySegmentTree<A, Concatenate, PushT>::get(ll id, ll l, ll r, ll tl, ll tr){
    if(r < tl or tr < l) return neutralElement;
    if(tl <= l and r <= tr){
        return a[id];
    }
    push(id, l, r);
    ll m=(l+r)/2;
    return con(get(2*id, l, m, tl, tr), get(2*id+1, m+1, r, tl, tr));
}

template<typename A, typename Concatenate, typename PushT>
void lazySegmentTree<A, Concatenate, PushT>::push(ll id, ll l, ll r) {
    ll m=(l+r)/2;
    a[2*id] = Push(a[2*id], p[id], m - l + 1);
    p[2*id] = con(p[2*id], p[id]);
    a[2*id+1] = Push(a[2*id+1], p[id], r - m);
    p[2*id+1] = con(p[2*id+1], p[id]);
    p[id] = neutralElement;
}

• 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