Submission #1037754

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037754		dwuy	Gift Exchange (JOI24_ho_t4)	C++14	100 / 100	1115 ms	177504 KiB

Main

/**         - dwuy -

　　　　　 ／＞　   フ
　　　　　 | 　_　 _|
　 　　　 ／`ミ _x ノ
　　 　 /　　　 　 |
　　　 /　  ヽ　　 ?
　／￣|　　 |　|　|
　| (￣ヽ＿_ヽ_)_)
　＼二つ

**/
#include <bits/stdc++.h>

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) (int)((s).size())
#define MASK(k)(1LL<<(k))
#define TASK "test"
#define int long long

using namespace std;

typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;

const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MX = 500005;

struct Node{ int mx, lz; };

struct SMT{
    int n;
    vector<Node> tree;

    SMT(int n=0){
        this->n = n;
        this->tree.assign(n<<2|3, {(int)-1e9, 0});
    }

    void down(int id){
        if(tree[id].lz == 0) return;
        int ID = id<<1;
        tree[ID].mx = tree[ID].lz = tree[id].lz;
        tree[ID|1].mx = tree[ID|1].lz = tree[id].lz;
        tree[id].lz = 0;
    }

    void update(int l, int r, int id, const int &u, const int &v, const int &val){
        if(l > v || r < u) return;
        if(l >=u && r <= v){
            tree[id].mx = val;
            tree[id].lz = val;
            return;
        }
        down(id);
        int mid = (l + r)>>1;
        update(l, mid, id<<1, u, v, val);
        update(mid + 1, r, id<<1|1, u, v, val);
        tree[id].mx = max(tree[id<<1].mx, tree[id<<1|1].mx);
    }

    void update(int l, int r, int val){
        update(1, n, 1, l, r, val);
    }

    int get(int l, int r, int id, const int &u, const int &v){
        if(l > v || r < u) return -1e9;
        if(l >= u && r <= v) return tree[id].mx;
        down(id);
        int mid = (l + r)>>1;
        return max(get(l, mid, id<<1, u, v), get(mid + 1, r, id<<1|1, u, v));
    }

    int get(int l, int r){
        return get(1, n, 1, l, r);
    }
};

struct BIT{
    int n;
    vector<int> tree;

    BIT(int n=0){
        this->n = n;
        this->tree.assign(n + 5, 0);
    }

    void update(int idx, int val){
        for(; idx<=n; idx+=-idx&idx) tree[idx] += val;
    }

    void update(int l, int r, int val){
        update(l, val);
        update(r + 1, -val);
    }

    int get(int idx){
        int res = 0;
        for(; idx; idx-=-idx&idx) res += tree[idx];
        return res;
    }
};

int n, q;
int a[MX];
int b[MX];
int f[MX];
int fr[MX];
int ans[MX];
vector<pii> qr[MX];
vector<int> G[MX];

void nhap(){
    cin >> n;
    for(int i=1; i<=n; i++) cin >> a[i];
    for(int i=1; i<=n; i++) cin >> b[i];
    cin >> q;
    for(int i=1; i<=q; i++){
        int l, r;
        cin >> l >> r;
        qr[r].push_back({l, i});
    }
}

void solve(){

    SMT smt(n<<1);
    for(int i=1; i<=n; i++){
        f[i] = max(0LL, smt.get(b[i], a[i])) + 1;
        smt.update(b[i], a[i], i);
    }
    smt = SMT(n<<1);
    for(int i=n; i>=1; i--){
        int p = -smt.get(b[i], a[i]);
        if(p <= n) G[p].push_back(i);
        smt.update(b[i], a[i], -i);
    }
    
    BIT bit(n<<1);
    for(int i=1; i<=n; i++){
        bit.update(f[i], i, 1);
        for(int u: G[i]) bit.update(f[u], u, -1);
        for(pii t: qr[i]) ans[t.se] = !!bit.get(t.fi);
    }
    for(int i=1; i<=q; i++) cout << (ans[i]? "No" : "Yes") << endl;
}

int32_t main(){
    fastIO;
    //file(TASK);

    nhap();
    solve();

    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