제출 #1139890

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1139890		VMaksimoski008	Gift Exchange (JOI24_ho_t4)	C++20	19 / 100	327 ms	150372 KiB

Main

#include <bits/stdc++.h>
#define ar array
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const ll inf = 1e18;
const int maxn = 1e5 + 5;

int pref[350][maxn];

signed main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);

    int n, q; cin >> n;
    vector<int> a(n+1), b(n+1);
    for(int i=1; i<=n; i++) cin >> a[i];
    for(int i=1; i<=n; i++) cin >> b[i];

    vector<int> L(n+1), R(n+1, n+1);
    map<int, vector<ar<int, 2> > > mp;
    for(int i=1; i<=n; i++) {
        mp[b[i]].push_back({ i, 1 });
        mp[a[i]].push_back({ i, -1 });
    }

    set<int> st;
    for(auto [p, vec] : mp) {
        for(auto [id, t] : vec) {
            if(t == -1) continue;
            auto it = st.lower_bound(id);
            if(it != st.end()) {
                R[id] = min(R[id], *it);
                L[*it] = max(L[*it], id);
            }

            if(!st.empty() && *st.begin() < id) {
                it = --st.lower_bound(id);
                R[*it] = min(R[*it], id);
                L[id] = max(L[id], *it);
            }

            st.insert(id);
        }

        for(auto [id, t] : vec)
            if(t == -1) st.erase(id);
    }

    const int B = sqrt(n);
    int cnt = 0;
    vector<int> lp(B+2), rp(B+2);
    for(int i=1; i<=(n+B-1)/B; i++) {
        lp[i] = rp[i-1] + 1;
        rp[i] = rp[i-1] + B;
        if(lp[i] > n) break;
        cnt++;
        rp[i] = min(rp[i], n);

        for(int j=lp[i]; j<=rp[i]; j++)
            pref[i][L[j]] = max(pref[i][L[j]], R[j]);
        for(int j=1; j<=n; j++) pref[i][j] = max(pref[i][j], pref[i][j-1]);
    }

    cin >> q;
    while(q--) {
        int l, r, ok=1; cin >> l >> r;

        for(int i=1; i<=cnt&&ok; i++) {
            if(lp[i] > n) break;
            // cout << lp[i] << " " << rp[i] << '\n';
            if(l <= lp[i] && rp[i] <= r) {
                if(pref[i][l-1] > r) ok = 0;
                // cout << "! 1\n";
            } else if(lp[i] <= l && r <= rp[i]) {
                for(int j=l; j<=r; j++)
                    if(L[j] < l && R[j] > r) ok = 0;
            } else if(lp[i] <= l && l <= rp[i]) {
                for(int j=l; j<=rp[i]; j++)
                    if(L[j] < l && R[j] > r) ok = 0;
                // cout << "! 2\n";
            } else if(lp[i] <= r && r <= rp[i]) {
                for(int j=lp[i]; j<=r; j++)
                    if(L[j] < l && R[j] > r) ok = 0;
                // cout << "! 3\n";
            }
        }
        
        cout << (ok ? "Yes" : "No") << '\n';
    }
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 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