제출 #1080026

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1080026		Thanhs	Long Mansion (JOI17_long_mansion)	C++14	25 / 100	3071 ms	52308 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;

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();
    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;
            if (l[i] == ll && r[i] == rr)
                break;
        }
    }
    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();

}

컴파일 시 표준 에러 (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 function 'int main()':
long_mansion.cpp:143:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |         freopen("in.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
long_mansion.cpp:144:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |         freopen("out.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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