Submission #1182621

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182621		jerzyk	Gift Exchange (JOI24_ho_t4)	C++20	100 / 100	571 ms	98944 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1<<20;
int ta[N], tb[N], l[N], r[N];
int drz[2][2 * N];
int sum[2 * N];
bool answer[N];
vector<int> en[N];
vector<pair<int, int>> que[N];

void Add(int v, int val)
{
    v += N;
    while(v > 0)
    {sum[v] += val; v /= 2;}
}

int Sum(int a, int b)
{
    a += N - 1; b += N + 1;
    int ans = 0;
    while(a / 2 != b / 2)
    {
        if(a % 2 == 0) ans += sum[a + 1];
        if(b % 2 == 1) ans += sum[b - 1];
        a /= 2; b /= 2;
    }
    return ans;
}

void UpdMa(int a, int b, int val)
{
    a += N - 1; b += N + 1;
    while(a / 2 != b / 2)
    {
        if(a % 2 == 0)
            drz[0][a + 1] = max(drz[0][a + 1], val);
        if(b % 2 == 1)
            drz[0][b - 1] = max(drz[0][b - 1], val);
        a /= 2;
        b /= 2;
    }
}

int Max(int v)
{
    v += N;
    int ans = -N;
    while(v > 0)
        {ans = max(ans, drz[0][v]); v /= 2;}
    return ans;
}

void UpdMa2(int v, int val)
{
    v += N;
    while(v > 0)
    {drz[1][v] = max(drz[1][v], val); v /= 2;}
}

int Max2(int a, int b)
{
    a += N - 1; b += N + 1;
    int ans = -N;
    while(a / 2 != b / 2)
    {
        if(a % 2 == 0)
            ans = max(ans, drz[1][a + 1]);
        if(b % 2 == 1)
            ans = max(ans, drz[1][b - 1]);
        a /= 2;
        b /= 2;
    }
    return ans;
}

inline void CntLR(int n)
{
    for(int i = 1; i <= n; ++i)
    {
        l[i] = max(Max(ta[i]), Max2(tb[i], ta[i]));
        UpdMa(tb[i], ta[i], i);
        UpdMa2(ta[i], i);
    }
    for(int i = 1; i <= N + 2 * n; ++i)
        {drz[0][i] = -N; drz[1][i] = -N;}
    for(int i = n; i >= 1; --i)
    {
        r[i] = -max(Max(ta[i]), Max2(tb[i], ta[i]));
        UpdMa(tb[i], ta[i], -i);
        UpdMa2(ta[i], -i);
        r[i] = min(r[i], n + 1);
        en[r[i]].pb(i);
        //cout << i << " " << l[i] << " " << r[i] << "\n";
    }
}

bool Check(int a, int b)
{
    for(int i = a; i <= b; ++i)
        if(l[i] < a && r[i] > b)
            return false;
    return true;
}

void Solve()
{
    int n, q, a, b;
    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> ta[i];
    for(int i = 1; i <= n; ++i)
        cin >> tb[i];
    CntLR(n);
    cin >> q;
    for(int i = 1; i <= q; ++i)
    {
        cin >> a >> b;
        que[b].pb(make_pair(a, i));
    }
    for(int i = 1; i <= n; ++i)
    {
        Add(i, 1); Add(l[i], -1);
        for(int j = 0; j < (int)en[i].size(); ++j)
        {
            Add(en[i][j], -1);
            Add(l[en[i][j]], 1);
        }
        for(int j = 0; j < (int)que[i].size(); ++j)
            answer[que[i][j].nd] = (Sum(que[i][j].st, i) == 0);
    }
    for(int i = 1; i <= q; ++i)
    {
        if(answer[i])
            cout << "Yes\n";
        else
            cout << "No\n";
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //int t; cin >> t;
    //while(t--)
        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