Submission #1209870

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209870		Hanksburger	Long Mansion (JOI17_long_mansion)	C++20	100 / 100	492 ms	89100 KiB

long_mansion

#include <bits/stdc++.h>
using namespace std;
int c[500005], d[500005], e[500005], X[500005], Y[500005], bit[500005], ans[500005], n, q;
vector<pair<pair<int, int>, pair<int, int> > > event;
vector<int> a[500005], store[500005];
void update(int x, int y)
{
    for (int i=x; i<=n; i+=i&(-i))
        bit[i]+=y;
}
int query(int x)
{
    int res=0;
    for (int i=x; i; i-=i&(-i))
        res+=bit[i];
    return res;
}
void solve(int t)
{
    for (int i=1; i<=n; i++)
        bit[i]=0;
    sort(event.begin(), event.end());
    int ind=0;
    set<int> s;
    for (int i=1; i<=n; i++)
    {
        while (ind<event.size() && event[ind].first.first==i)
        {
            if (event[ind].first.second)
            {
                if (query(event[ind].second.first-1)==query(event[ind].second.second))
                    ans[event[ind].first.second]=1;
            }
            else if (event[ind].second.first)
            {
                if (t)
                {
                    while (s.size() && *prev(s.end())>=event[ind].second.second)
                    {
                        update(*prev(s.end()), 1);
                        s.erase(prev(s.end()));
                    }
                }
                else
                {
                    while (s.size() && *s.begin()<=event[ind].second.second)
                    {
                        update(*s.begin(), 1);
                        s.erase(s.begin());
                    }
                }
            }
            else
                s.insert(event[ind].second.second);
            ind++;
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i=1; i<n; i++)
        cin >> c[i];
    for (int i=1; i<=n; i++)
    {
        int m;
        cin >> m;
        while (m--)
        {
            int x;
            cin >> x;
            a[i].push_back(x);
        }
        d[i]=n+1;
    }
    for (int i=1; i<=n; i++)
    {
        store[c[i-1]].push_back(i);
        for (int x:a[i])
        {
            for (int y:store[x])
                d[y]=i;
            store[x].clear();
        }
    }
    for (int i=1; i<=n; i++)
        store[i].clear();
    for (int i=n; i>=1; i--)
    {
        store[c[i]].push_back(i);
        for (int x:a[i])
        {
            for (int y:store[x])
                e[y]=i;
            store[x].clear();
        }
    }
    cin >> q;
    for (int i=1; i<=q; i++)
        cin >> X[i] >> Y[i];
    for (int i=1; i<=n; i++)
    {
        event.push_back({{e[i]+1, 0}, {0, i}});
        event.push_back({{i, 0}, {1, d[i]-1}});
    }
    for (int i=1; i<=q; i++)
        if (X[i]<Y[i])
            event.push_back({{X[i], i}, {X[i], Y[i]-1}});
    solve(0);
    event.clear();
    for (int i=1; i<=n; i++)
    {
        event.push_back({{n-d[i]+2, 0}, {0, i}});
        event.push_back({{n-i+1, 0}, {1, e[i]+1}});
    }
    for (int i=1; i<=q; i++)
        if (X[i]>Y[i])
            event.push_back({{n-X[i]+1, i}, {Y[i]+1, X[i]}});
    solve(1);
    for (int i=1; i<=q; i++)
        cout << (ans[i]?"YES":"NO") << '\n';
}

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