Submission #1191048

#TimeUsernameProblemLanguageResultExecution timeMemory
1191048patgraGift Exchange (JOI24_ho_t4)C++20
50 / 100
2597 ms35316 KiB
#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back

using namespace std;

int n, q, maxLog;
vector<vector<pair<int, int>>> stMaxA, stMaxB;
vector<int> a, b;

pair<int, int> stQ(int l, int r, bool isA) {
    int k = 31 - __builtin_clz(r - l + 1);
    return isA ? max(stMaxA[l][k], stMaxA[r - (1 << k) + 1][k]) : max(stMaxB[l][k], stMaxB[r - (1 << k) + 1][k]);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> n;
    a.resize(n); b.resize(n);
    rep(i, 0, n) cin >> a[i];
    rep(i, 0, n) cin >> b[i];
    maxLog = 32 - __builtin_clz(n);
    stMaxA.resize(n, vector<pair<int, int>>(maxLog));
    stMaxB.resize(n, vector<pair<int, int>>(maxLog));
    rep(i, 0, n) stMaxA[i][0] = {a[i], i}, stMaxB[i][0] = {b[i], i};
    rep(k, 1, maxLog) rep(i, 0, n) stMaxA[i][k] = max(stMaxA[i][k - 1], stMaxA[min(n - 1, i + (1 << (k - 1)))][k - 1]);
    rep(k, 1, maxLog) rep(i, 0, n) stMaxB[i][k] = max(stMaxB[i][k - 1], stMaxB[min(n - 1, i + (1 << (k - 1)))][k - 1]);
    cin >> q;
    rep(_, 0, q) {
        int l, r;
        cin >> l >> r;
        l--; r--;
        DC << l << ' ' << r << eol;
        vector<int> aa, bb;
        rep(i, l, r + 1) aa.pb(a[i]), bb.pb(b[i]);
        ranges::sort(aa), ranges::sort(bb);
        auto itA = 0;
        bool g = true, g2 = true;
        DC << ' ';
        repIn(i, aa) DC << i << ' '; 
        DC << eol;
        DC << ' ';
        repIn(i, bb) DC << i << ' '; 
        DC << eol;
        rep(i, 0, r - l + 1) {
            while(itA < r - l + 1 && aa[itA] < bb[i]) itA++;
            DC << ' ' << i << ' ' << itA << eol;
            if(itA > i) { g = false; break; }
            if(itA == i) {
                if(g2) { g2 = false; continue; }
                else { g = false; break; }
            }
            g2 = true;
        }
        cout << (g && g2 ? "Yes" : "No") << eol;
    }
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...