Submission #1080049

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1080049	2024-08-29T06:35:49 Z	vjudge1	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	344 ms	62596 KB

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

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.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	29276 KB	Output is correct
2	Correct	6 ms	29276 KB	Output is correct
3	Correct	6 ms	29532 KB	Output is correct
4	Correct	8 ms	29276 KB	Output is correct
5	Correct	8 ms	29284 KB	Output is correct
6	Correct	6 ms	29276 KB	Output is correct
7	Correct	7 ms	29272 KB	Output is correct

Subtask #2

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	29276 KB	Output is correct
2	Correct	6 ms	29276 KB	Output is correct
3	Correct	6 ms	29532 KB	Output is correct
4	Correct	8 ms	29276 KB	Output is correct
5	Correct	8 ms	29284 KB	Output is correct
6	Correct	6 ms	29276 KB	Output is correct
7	Correct	7 ms	29272 KB	Output is correct
8	Correct	91 ms	30876 KB	Output is correct
9	Correct	70 ms	30736 KB	Output is correct
10	Correct	97 ms	31060 KB	Output is correct
11	Correct	66 ms	31060 KB	Output is correct
12	Correct	61 ms	28936 KB	Output is correct
13	Correct	87 ms	31152 KB	Output is correct
14	Correct	94 ms	30992 KB	Output is correct
15	Correct	90 ms	31244 KB	Output is correct
16	Correct	58 ms	31312 KB	Output is correct
17	Correct	66 ms	30936 KB	Output is correct
18	Correct	83 ms	30988 KB	Output is correct
19	Correct	96 ms	30964 KB	Output is correct
20	Correct	65 ms	31208 KB	Output is correct
21	Correct	84 ms	31316 KB	Output is correct
22	Correct	57 ms	31056 KB	Output is correct
23	Correct	97 ms	30768 KB	Output is correct
24	Correct	62 ms	30804 KB	Output is correct
25	Correct	66 ms	30844 KB	Output is correct
26	Correct	73 ms	30888 KB	Output is correct

Subtask #3

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	141 ms	37208 KB	Output is correct
2	Correct	155 ms	37024 KB	Output is correct
3	Correct	142 ms	36952 KB	Output is correct
4	Correct	141 ms	37196 KB	Output is correct
5	Correct	140 ms	37116 KB	Output is correct
6	Correct	163 ms	36696 KB	Output is correct
7	Correct	129 ms	36688 KB	Output is correct
8	Correct	111 ms	36716 KB	Output is correct
9	Correct	114 ms	36696 KB	Output is correct
10	Correct	115 ms	36688 KB	Output is correct
11	Correct	114 ms	36728 KB	Output is correct

Subtask #4

75.0 / 75.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	29276 KB	Output is correct
2	Correct	6 ms	29276 KB	Output is correct
3	Correct	6 ms	29532 KB	Output is correct
4	Correct	8 ms	29276 KB	Output is correct
5	Correct	8 ms	29284 KB	Output is correct
6	Correct	6 ms	29276 KB	Output is correct
7	Correct	7 ms	29272 KB	Output is correct
8	Correct	91 ms	30876 KB	Output is correct
9	Correct	70 ms	30736 KB	Output is correct
10	Correct	97 ms	31060 KB	Output is correct
11	Correct	66 ms	31060 KB	Output is correct
12	Correct	61 ms	28936 KB	Output is correct
13	Correct	87 ms	31152 KB	Output is correct
14	Correct	94 ms	30992 KB	Output is correct
15	Correct	90 ms	31244 KB	Output is correct
16	Correct	58 ms	31312 KB	Output is correct
17	Correct	66 ms	30936 KB	Output is correct
18	Correct	83 ms	30988 KB	Output is correct
19	Correct	96 ms	30964 KB	Output is correct
20	Correct	65 ms	31208 KB	Output is correct
21	Correct	84 ms	31316 KB	Output is correct
22	Correct	57 ms	31056 KB	Output is correct
23	Correct	97 ms	30768 KB	Output is correct
24	Correct	62 ms	30804 KB	Output is correct
25	Correct	66 ms	30844 KB	Output is correct
26	Correct	73 ms	30888 KB	Output is correct
27	Correct	141 ms	37208 KB	Output is correct
28	Correct	155 ms	37024 KB	Output is correct
29	Correct	142 ms	36952 KB	Output is correct
30	Correct	141 ms	37196 KB	Output is correct
31	Correct	140 ms	37116 KB	Output is correct
32	Correct	163 ms	36696 KB	Output is correct
33	Correct	129 ms	36688 KB	Output is correct
34	Correct	111 ms	36716 KB	Output is correct
35	Correct	114 ms	36696 KB	Output is correct
36	Correct	115 ms	36688 KB	Output is correct
37	Correct	114 ms	36728 KB	Output is correct
38	Correct	236 ms	59004 KB	Output is correct
39	Correct	307 ms	62288 KB	Output is correct
40	Correct	201 ms	55376 KB	Output is correct
41	Correct	344 ms	62596 KB	Output is correct
42	Correct	135 ms	36436 KB	Output is correct
43	Correct	135 ms	36436 KB	Output is correct
44	Correct	230 ms	43856 KB	Output is correct
45	Correct	207 ms	43800 KB	Output is correct
46	Correct	238 ms	43860 KB	Output is correct
47	Correct	128 ms	36684 KB	Output is correct
48	Correct	145 ms	36692 KB	Output is correct
49	Correct	237 ms	43924 KB	Output is correct
50	Correct	227 ms	44024 KB	Output is correct
51	Correct	240 ms	43908 KB	Output is correct
52	Correct	190 ms	43740 KB	Output is correct
53	Correct	262 ms	55376 KB	Output is correct
54	Correct	317 ms	58960 KB	Output is correct
55	Correct	241 ms	55376 KB	Output is correct