Submission #1080047

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080047		Thanhs	Long Mansion (JOI17_long_mansion)	C++14	100 / 100	391 ms	73736 KiB

long_mansion

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define double long double
 
#define endl '\n'
#define fastIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define setmin(x, y) x = min((x), (y))
#define setmax(x, y) x = max((x), (y))
#define sqr(x) ((x) * (x))
#define fi first
#define se second
#define aint(x) x.begin(), x.end()
 
// mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count());
// int rand(int l, int r){return l + ((hdp() % (r - l + 1)) + r - l + 1) % (r - l + 1);}

const int NM = 5e5 + 5;

int n, b[NM], c[NM], a[NM], L[NM];

struct ST1
{
    int dt[4 * NM];
    void build(int x = 1, int l = 1, int r = n)
    {
        if (l == r)
        {
            dt[x] = b[l];
            return;
        }
        int m = l + r >> 1;
        build(x << 1, l, m);
        build(x << 1 | 1, m + 1, r);
        dt[x] = min(dt[x << 1], dt[x << 1 | 1]);
    }
    int get(int i, int l, int x = 1, int lx = 1, int rx = n)
    {
        // cout << i << ' ' << l << ' ' << x << ' ' << lx << ' ' << rx << endl;
        if (rx < l || dt[x] >= i)
            return rx + 1;
        if (lx == rx)
            return lx;
        int m = lx + rx >> 1;
        int res = m + 1;
        if (dt[x << 1] < i)
            res = get(i, l, x << 1, lx, m);
        if (res != m + 1)
            return res;
        return get(i, l, x << 1 | 1, m + 1, rx);
    }
}st1;

struct ST2
{
    int dt[4 * NM];
    void build(int x = 1, int l = 1, int r = n)
    {
        if (l == r)
        {
            dt[x] = c[l + 1];
            return;
        }
        int m = l + r >> 1;
        build(x << 1, l, m);
        build(x << 1 | 1, m + 1, r);
        dt[x] = max(dt[x << 1], dt[x << 1 | 1]);
    }
    int get(int i, int r, int x = 1, int lx = 1, int rx = n)
    {
        if (lx > r || dt[x] <= i)
            return lx - 1;
        if (lx == rx)
            return lx;
        int m = lx + rx >> 1;
        int res = m;
        if (dt[x << 1 | 1] > i)
            res = get(i, r, x << 1 | 1, m + 1, rx);
        if (res != m)
            return res;
        return get(i, r, x << 1, lx, m);
    }
}st2;

struct ST3
{
    pair<int, int> dt[4 * NM];
    void build(int x = 1, int l = 1, int r = n)
    {
        dt[x] = {n + 1, 0};
        if (l == r)
            return;
        int m = l + r >> 1;
        build(x << 1, l, m);
        build(x << 1 | 1, m + 1, r);
    }
    void upd(pair<int, int> v, int i, int x = 1, int lx = 1, int rx = n)
    {
        if (lx == rx)
        {
            dt[x] = v;
            return;
        }
        int m = lx + rx >> 1;
        if (m >= i)
            upd(v, i, x << 1, lx, m);
        else
            upd(v, i, x << 1 | 1, m + 1, rx);
        dt[x].fi = min(dt[x << 1].fi, dt[x << 1 | 1].fi);
        dt[x].se = max(dt[x << 1].se, dt[x << 1 | 1].se);
    }
    pair<int, int> get(int l, int r, int x = 1, int lx = 1, int rx = n)
    {
        if (l > rx || lx > r || l > r)
            return {n + 1, 0};
        if (lx >= l && rx <= r)
            return dt[x];
        int m = lx + rx >> 1;
        pair<int, int> res1 = get(l, r, x << 1, lx, m);
        pair<int, int> res2 = get(l, r, x << 1 | 1, m + 1, rx);
        return {min(res1.fi, res2.fi), max(res1.se, res2.se)};
    }
}st3;

int l[NM], r[NM];
vector<int> v[NM];

void solve()
{
    cin >> n;
    for (int i = 2; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
    {
        b[i] = L[a[i]];
        int t; cin >> t;
        while (t--)
        {
            int x;
            cin >> x;
            setmax(L[x], i);
            v[i].push_back(x);
        }
    }
    for (int i = 1; i <= n; i++)
        L[i] = n + 1;
    for (int i = n; i >= 1; i--)
    {
        for (auto x : v[i])
            setmin(L[x], i);
        c[i] = L[a[i]];
    }
    b[1] = n + 1;
    st1.build();
    st2.build();
    st3.build();
    for (int i = 1; i <= n; i++)
    {
        l[i] = r[i] = i;
        while (1)
        {
            int ll = l[i], rr = r[i];
            r[i] = st1.get(l[i], i + 1) - 1;
            l[i] = st2.get(r[i], i - 1) + 1;
            pair<int, int> res = st3.get(l[i], i - 1);
            setmin(l[i], res.fi);
            setmax(r[i], res.se);
            if (l[i] == ll && r[i] == rr)
                break;
        }
        st3.upd({l[i], r[i]}, i);
    }
    int q;
    cin >> q;
    while (q--)
    {
        int x, y;
        cin >> x >> y;
        cout << (l[x] <= y && r[x] >= y ? "YES\n" : "NO\n");
    }
}

int main()
{
    fastIO
    if (fopen("in.txt", "r")) 
    {
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    }
    int tc = 1; // cin >> tc;
    while (tc--)
        solve();

}

Compilation message (stderr)

long_mansion.cpp: In member function 'void ST1::build(int, int, int)':
long_mansion.cpp:32:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |         int m = l + r >> 1;
      |                 ~~^~~
long_mansion.cpp: In member function 'int ST1::get(int, int, int, int, int)':
long_mansion.cpp:44:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |         int m = lx + rx >> 1;
      |                 ~~~^~~~
long_mansion.cpp: In member function 'void ST2::build(int, int, int)':
long_mansion.cpp:64:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |         int m = l + r >> 1;
      |                 ~~^~~
long_mansion.cpp: In member function 'int ST2::get(int, int, int, int, int)':
long_mansion.cpp:75:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |         int m = lx + rx >> 1;
      |                 ~~~^~~~
long_mansion.cpp: In member function 'void ST3::build(int, int, int)':
long_mansion.cpp:93:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   93 |         int m = l + r >> 1;
      |                 ~~^~~
long_mansion.cpp: In member function 'void ST3::upd(std::pair<int, int>, int, int, int, int)':
long_mansion.cpp:104:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  104 |         int m = lx + rx >> 1;
      |                 ~~~^~~~
long_mansion.cpp: In member function 'std::pair<int, int> ST3::get(int, int, int, int, int)':
long_mansion.cpp:118:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  118 |         int m = lx + rx >> 1;
      |                 ~~~^~~~
long_mansion.cpp: In function 'int main()':
long_mansion.cpp:188:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  188 |         freopen("in.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
long_mansion.cpp:189:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  189 |         freopen("out.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 75 / 75