Submission #801450

#	Time	Username	Problem	Language	Result	Execution time	Memory
801450		vjudge1	Long Mansion (JOI17_long_mansion)	C++14	10 / 100	3072 ms	79544 KiB

long_mansion

#include<bits/stdc++.h>
using namespace std ;
const int N = (1 << 19), NS = 5e3, NSS = (1 << 17) ;
bool flag, us[NS + 1][NS + 1] ;
int n, q, sm, c[N + 1] ;
vector<int> sg[2 * NSS + 1], sg_b[2 * NSS + 1] ;
vector<int> nul, ks[N + 1] ;
map<int, int> ch, null ;
void bfs(int city)
{
    ch = null ;
    bool abu = 1 ;
    int l = city, r = city ;
    for(int i : ks[city])
        ch[i] = 1 ;
    us[city][city] = 1 ;
    while(abu)
    {
        abu ^= 1 ;
        if(l > 1 && ch[c[l - 1]])
        {
            l-- ;
            for(int i : ks[l])
                ch[i] = 1 ;
            us[city][l] = 1 ;
            abu |= 1 ;
        }
        if(r < n && ch[c[r]])
        {
            abu |= 1 ;
            r++ ;
            for(int i : ks[r])
                ch[i] = 1 ;
            us[city][r] = 1 ;
        }
    }
}
vector<int> mrg(vector<int> a, vector<int> b)
{
    if(!a.size() || !b.size())
    {
        if(a.size())
            return a ;
        else
            return b ;
    }
    int uk1 = 0, uk2 = 0 ;
    vector<int> c ;
    while(uk1 < a.size() || uk2 < b.size())
    {
        int mn = 21 ;
        if(uk1 < a.size())
            mn = min(mn, a[uk1]) ;
        if(uk2 < b.size())
            mn = min(mn, b[uk2]) ;
        if(!c.size() || c.back() != mn)
            c.push_back(mn) ;
        if(uk1 < a.size() && a[uk1] == mn)
            uk1++ ;
        else
            uk2++ ;
    }
    return c ;
}
void build(int l, int r, int v)
{
    if(l == r)
    {
        if(l <= n)
        {
            for(int j : ks[l])
                sg_b[v].push_back(j) ;
        }
        if(l < n)
            sg[v].push_back(c[l]) ;
        return ;
    }
    int mid = (l + r) >> 1 ;
    build(l, mid, v * 2) ;
    build(mid + 1, r, v * 2 + 1) ;
    sg[v] = mrg(sg[v * 2], sg[v * 2 + 1]) ;
    sg_b[v] = mrg(sg_b[v * 2], sg_b[v * 2 + 1]) ;
}
vector<int> get_all(int l, int r, int l1, int r1, int v)
{
    if(l > r1 || r < l1)
        return nul ;
    if(l1 <= l && r <= r1)
        return sg[v] ;
    int mid = (l + r) >> 1 ;
    return mrg(get_all(l, mid, l1, r1, v * 2), get_all(mid + 1, r, l1, r1, v * 2 + 1)) ;
}
vector<int> get_all_b(int l, int r, int l1, int r1, int v)
{
    if(l > r1 || r < l1)
        return nul ;
    if(l1 <= l && r <= r1)
        return sg_b[v] ;
    int mid = (l + r) >> 1 ;
    return mrg(get_all_b(l, mid, l1, r1, v * 2), get_all_b(mid + 1, r, l1, r1, v * 2 + 1)) ;
}
signed main()
{
    ios_base::sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cout.tie( 0 ) ;
    cin >> n ;
    for(int i = 1 ; i < n ; i++)
    {
        cin >> c[i] ;
        if(c[i] > 20)flag = 1 ;
    }
    for(int i = 1 ; i <= n ; i++)
    {
        int b ;
        cin >> b ;
        sm += b ;
        for(int j = 1 ; j <= b ; j++)
        {
            int a ;
            cin >> a ;
            if(a > 20)flag = 1 ;
            ks[i].push_back(a) ;
        }
    }
    cin >> q ;
    if(n <= 5000 && sm <= 5000)
    {
        for(int i = 1 ; i <= n ; i++)
            bfs(i) ;
        for(int i = 1 ; i <= q ; i++)
        {
            int x, y ;
            cin >> x >> y ;
            if(us[x][y])
                cout << "YES\n" ;
            else
                cout << "NO\n" ;
        }
        return 0 ;
    }
    if(n <= 1e5 && !flag)
    {
        build(1, NSS, 1) ;
        while(q--)
        {
            bool abu[21] = {} ;
            bool fl = 1 ;
            int x, y ;
            cin >> x >> y ;
            int lf = x, rg = x ;
            for(int j : ks[x])
                abu[j] = 1 ;
            while(fl)
            {
//                cout<<lf<< ' '<<rg<<'\n' ;
                fl ^= 1 ;
                vector<int> vl, vr ;
                int l = 0, r = lf ;
                while(l + 1 < r)
                {
                    bool check = 0 ;
                    int mid = (l + r) >> 1 ;
                    vl = get_all(1, NSS, mid, lf - 1, 1) ;
                    for(int j : vl)
                        if(!abu[j])check = 1 ;
//                    cout<<"1- "<<check<<' '<<mid << '\n';
                    if(check)
                        l = mid ;
                    else
                        r = mid ;
                }
//                cout << l << ' ' << r << '\n' ;
                if(r < lf)
                {
                    vl = get_all_b(1, NSS, r, lf - 1, 1) ;
                    for(int j : vl)
                    {
//                        cout << "1+ " << j << '\n' ;
                        abu[j] = 1 ;
                    }
                    lf = r ;
                    fl = 1 ;
                }
                l = rg - 1, r = n ;
                while(l + 1 < r)
                {
                    bool check = 0 ;
                    int mid = (l + r) >> 1 ;
//                    cout<<"2- "<<check<<' '<<mid << '\n';
                    vr = get_all(1, NSS, rg, mid, 1) ;
                    for(int j : vr)
                    {
                        if(!abu[j])check = 1 ;
                    }
                    if(check)
                        r = mid ;
                    else
                        l = mid ;
                }
//                cout << l << ' ' << r << '\n' ;
                if(l >= rg)
                {
                    vr = get_all_b(1, NSS, rg + 1, l + 1, 1) ;
                    for(int j : vr)
                        abu[j] = 1 ;
                    fl = 1 ;
                    rg = l + 1 ;
                }
//                cout<<"_____________________\n" ;
            }
            if(lf <= y && y <= rg)
                cout << "YES\n" ;
            else
                cout << "NO\n" ;
        }
        return 0 ;
    }
    return 0 ;
}

Compilation message (stderr)

long_mansion.cpp: In function 'std::vector<int> mrg(std::vector<int>, std::vector<int>)':
long_mansion.cpp:49:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     while(uk1 < a.size() || uk2 < b.size())
      |           ~~~~^~~~~~~~~~
long_mansion.cpp:49:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     while(uk1 < a.size() || uk2 < b.size())
      |                             ~~~~^~~~~~~~~~
long_mansion.cpp:52:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         if(uk1 < a.size())
      |            ~~~~^~~~~~~~~~
long_mansion.cpp:54:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         if(uk2 < b.size())
      |            ~~~~^~~~~~~~~~
long_mansion.cpp:58:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         if(uk1 < a.size() && a[uk1] == mn)
      |            ~~~~^~~~~~~~~~

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