Submission #1216373

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216373		badge881	Gift Exchange (JOI24_ho_t4)	C++20	100 / 100	1323 ms	144164 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int mxn = 1e6 + 5;

struct seg
{
    int t[8 * mxn]{0}, lz[8 * mxn]{0};
    void build(int x)
    {
        for (int i = 0; i < 4 * mxn; i++)
            t[i] = x, lz[i] = 1e9;
    }
    void push(int i, int l, int r)
    {
        t[i] = min(lz[i], t[i]);
        if (l < r)
            lz[2 * i] = min(lz[i], lz[2 * i]), lz[2 * i + 1] = min(lz[2 * i + 1], lz[i]);
        lz[i] = 1e9;
    }
    void upd(int i, int l, int r, int tl, int tr, int v)
    {
        push(i, l, r);
        if (r < tl || l > tr)
            return;
        if (r <= tr && l >= tl)
        {
            lz[i] = min(lz[i], v);
            push(i, l, r);
            return;
        }
        int m = (l + r) >> 1;
        upd(2 * i, l, m, tl, tr, v);
        upd(2 * i + 1, m + 1, r, tl, tr, v);
        t[i] = min(t[2 * i], t[2 * i + 1]);
    }
    int qr(int i, int l, int r, int tl, int tr)
    {
        push(i, l, r);
        if (r < tl || l > tr)
            return 1e9;
        if (r <= tr && l >= tl)
            return t[i];
        int m = (l + r) >> 1;
        return min(qr(2 * i, l, m, tl, tr), qr(2 * i + 1, m + 1, r, tl, tr));
    }
} sl, sr;

int a[mxn], b[mxn], l[mxn], r[mxn], ans[mxn];
int sg[2 * mxn]{0};

void upd(int i, int sz, int amt)
{
    i += sz;
    sg[i] = amt;
    for (i >>= 1; i; i >>= 1)
        sg[i] = min(sg[2 * i], sg[2 * i + 1]);
}

int qr(int l, int r, int sz, int rs = 1e9)
{
    for (l += sz, r += sz; l < r; l >>= 1, r >>= 1)
    {
        if (l & 1)
            rs = min(rs, sg[l++]);
        if (r & 1)
            rs = min(rs, sg[--r]);
    }
    return rs;
}
vector<int> up[mxn];
vector<pair<int, int>> query[mxn];
int main()
{
    int n;
    scanf("%d", &n);
    sl.build(0);
    sr.build(1e9);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++)
        scanf("%d", &b[i]);
    for (int i = 1; i <= n; i++)
    {
        l[i] = -sl.qr(1, 1, 2 * n, b[i], a[i]);
        sl.upd(1, 1, 2 * n, b[i], a[i], -i);
    }
    for (int i = 1; i <= n; i++)
        sg[i + n - 1] = l[i];
    for (int i = n - 1; i > 0; i--)
        sg[i] = min(sg[2 * i], sg[2 * i + 1]);
    for (int i = n; i >= 1; i--)
    {
        r[i] = sr.qr(1, 1, 2 * n, b[i], a[i]);
        sr.upd(1, 1, 2 * n, b[i], a[i], i);
    }
    for (int i = 1; i <= n; i++)
    {
        if (r[i] == 1e9)
            continue;
        up[r[i]].push_back(i);
    }
    int q;
    scanf("%d", &q);
    for (int i = 1; i <= q; i++)
    {
        int l, r;
        scanf("%d %d", &l, &r);
        query[r].push_back({l, i});
    }
    for (int i = 1; i <= n; i++)
    {
        for (auto it : up[i])
            upd(it - 1, n, 1e9);
        for (auto [tl, id] : query[i])
            ans[id] = (qr(tl - 1, i, n) >= tl ? 1 : 0);
    }
    for (int i = 1; i <= q; i++)
        printf(ans[i] ? "Yes\n" : "No\n");
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:76:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
Main.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         scanf("%d", &a[i]);
      |         ~~~~~^~~~~~~~~~~~~
Main.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |         scanf("%d", &b[i]);
      |         ~~~~~^~~~~~~~~~~~~
Main.cpp:104:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
Main.cpp:108:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |         scanf("%d %d", &l, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~~

• 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