Submission #447761

#	Time	Username	Problem	Language	Result	Execution time	Memory
447761		blue	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	1929 ms	143556 KiB

long_mansion

#include <iostream>
#include <vector>
#include <stack>
#include <set>
using namespace std;

const int INF = 1e9;

const int maxN = 500'000;
const int lgN = 19;




int N;
vector<int> C(1+maxN+1);
vector<int> key_pos_list[1+maxN+1];




vector<int> left_key_pos(1+maxN+1);
vector<int> right_key_pos(1+maxN+1);




vector<int> go_left(1+maxN+1);
vector<int> go_right(1+maxN+1);



bool queryAdj(int i, int j)
{
    if(i == 0 || i == N+1) return 1;

    if(j == i+1) return (go_left[i] <= right_key_pos[i]);
    else if(j == i-1) return (left_key_pos[i] <= go_right[i]);
    else
    {
        cout << "ERROR\n";
        return 0;
    }
}



vector<int> left_reach(1+maxN+1);
vector<int> right_reach(1+maxN+1);







struct segtree
{
    int l;
    int r;

    int mn = 0;
    int mx = 0;

    segtree* left = NULL;
    segtree* right = NULL;

    segtree()
    {
        ;
    }

    segtree(int L, int R)
    {
        l = L;
        r = R;
        if(l == r) return;
        int m = (l+r)/2;
        left = new segtree(l, m);
        right = new segtree(m+1, r);
    }

    void update(int I, int V)
    {
        if(I < l || r < I) return;
        else if(l == r)
        {
            mn = mx = V;
        }
        else
        {
            left->update(I, V);
            right->update(I, V);
            mn = min(left->mn, right->mn);
            mx = max(left->mx, right->mx);
        }
    }

    int rangemax(int L, int R)
    {
        if(R < l || r < L) return -INF;
        else if(L <= l && r <= R)
        {
            return mx;
        }
        else
        {
            return max(left->rangemax(L, R), right->rangemax(L, R));
        }
    }

    int rangemin(int L, int R)
    {
        if(R < l || r < L) return INF;
        else if(L <= l && r <= R)
        {
            return mn;
        }
        else
        {
            return min(left->rangemin(L, R), right->rangemin(L, R));
        }
    }
};





int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

//PART 0: INPUT
    cin >> N;

    for(int i = 1; i+1 <= N; i++)
        cin >> C[i];

    for(int k = 1; k <= N; k++)
        key_pos_list[k].push_back(0);

    for(int i = 1; i <= N; i++)
    {
        int B;
        cin >> B;

        for(int j = 1; j <= B; j++)
        {
            int A;
            cin >> A;

            key_pos_list[A].push_back(i);
        }
    }

    for(int k = 1; k <= N; k++)
        key_pos_list[k].push_back(N+1);









//PART 1: left_key_pos, right_key_pos;

    left_key_pos[1] = N+1;
    for(int i = 2; i <= N; i++)
    {
        int ind = -1;
        for(int bit = lgN; bit >= 0; bit--)
        {
            if(ind + (1 << bit) >= key_pos_list[ C[i-1] ].size()) continue;
            if(key_pos_list[ C[i-1] ][ind + (1 << bit)] >= i) continue;
            ind += (1 << bit);
        }
        ind++;
        left_key_pos[i] = key_pos_list[ C[i-1] ][ind];
    }

    segtree left_key_segtree(1, N);
    for(int i = 1; i <= N; i++) left_key_segtree.update(i, left_key_pos[i]);


    right_key_pos[N] = 0;
    for(int i = N-1; i >= 1; i--)
    {
        int ind = -1;
        for(int bit = lgN; bit >= 0; bit--)
        {
            if(ind + (1 << bit) >= key_pos_list[ C[i] ].size()) continue;
            if(key_pos_list[ C[i] ][ind + (1 << bit)] > i) continue;
            ind += (1 << bit);
        }
        right_key_pos[i] = key_pos_list[ C[i] ][ind];
    }

    segtree right_key_segtree(1, N);
    for(int i = 1; i <= N; i++) right_key_segtree.update(i, right_key_pos[i]);











// PART 2: go_left, go_right;

    stack<int> left_wall;
    for(int i = 1; i <= N; i++)
    {
        // cerr << "i = " << i << '\n';
        left_wall.push(i);
        while(left_key_pos[ left_wall.top() ] <= i)
            left_wall.pop();

        go_left[i] = left_wall.top();
    }

    stack<int> right_wall;
    for(int i = N; i >= 1; i--)
    {
        // cerr << "i = " << i << '\n';
        right_wall.push(i);
        while(right_key_pos[ right_wall.top() ] >= i)
            right_wall.pop();

        go_right[i] = right_wall.top();
    }

    // cerr << "\n\n";
    // for(int i = 1; i <= N; i++) cerr << go_left[i] << ' ' << go_right[i] << '\n';





    //left_wall and right_wall are now used differently.


//PART 3: left_reach

    vector<int> tmp;


    while(!left_wall.empty()) left_wall.pop();

    for(int i = 1; i <= N; i++)
    {
        // cerr << "\n\n\n";
        // cerr << "i = " << i << '\n';
        if(queryAdj(i, i-1) == 0) //i is start of LC
        {
            left_reach[i] = i;
            left_wall.push(i);

            // cerr << "case 1: " << left_reach[i] << '\n';
        }
        else
        {
            // cerr << "case 2 \n";
            int curr_go_right = go_right[i];
            // while(left_key_pos[ left_wall.top() ] <= go_right[i]) //do a binary search!!!!!
            //     left_wall.pop();

            // cerr << left_wall.top() << ' ' << left_key_pos[left_wall.top()] << ' ' << curr_go_right << '\n';
            for(int bit = lgN; bit >= 0; bit--)
            {
                int new_go_right = curr_go_right + (1 << bit);
                if(new_go_right > N) continue;

                if(left_wall.top() <= right_key_segtree.rangemin(i, new_go_right - 1))
                    curr_go_right = new_go_right;
            }


            while(left_key_pos[ left_wall.top() ] <= curr_go_right)
            {
                left_wall.pop();

                for(int bit = lgN; bit >= 0; bit--)
                {
                    int new_go_right = curr_go_right + (1 << bit);
                    if(new_go_right > N) continue;

                    if(left_wall.top() <= right_key_segtree.rangemin(i, new_go_right - 1))
                        curr_go_right = new_go_right;
                }

                // cerr << left_wall.top() << ' ' << left_key_pos[left_wall.top()] << ' ' << curr_go_right << '\n';
            }

            left_reach[i] = left_wall.top();
            for(int t: tmp) left_reach[t] = left_reach[i];
            tmp.clear();
        }
    }








//PART 4: right_reach


    tmp.clear();

    while(!right_wall.empty()) right_wall.pop();

    for(int i = N; i >= 1; i--)
    {
        // cerr << "\n\n\n";
        // cerr << "i = " << i << '\n';
        if(queryAdj(i, i+1) == 0)
        {
            right_reach[i] = i;
            right_wall.push(i);
        }
        else
        {
            int curr_go_left = go_left[i];

            // while(right_key_pos[ right_wall.top() ] >= i) //do a binary search!!!!!
            //     right_wall.pop();

            // cerr << right_wall.top() << ' ' << right_key_pos[ right_wall.top() ] << ' ' << curr_go_left << '\n';
            while(1)
            {
                for(int bit = lgN; bit >= 0; bit--)
                {
                    int new_go_left = curr_go_left - (1 << bit);
                    if(new_go_left < 1) continue;

                    if(right_wall.top() >= left_key_segtree.rangemax(new_go_left + 1, i))
                        curr_go_left = new_go_left;
                }

                if(right_key_pos[ right_wall.top() ] < curr_go_left)
                    break;

                right_wall.pop();
            }


            right_reach[i] = right_wall.top();
            for(int t: tmp) right_reach[t] = right_reach[i];
            tmp.clear();
        }
    }






    // cerr << "\n\n\n";



//PART 5: QUERIES
    // for(int i = 1; i <= N; i++) cerr << i << ": " << left_reach[i] << ' ' << right_reach[i] << '\n';


    int Q;
    cin >> Q;

    for(int q = 1; q <= Q; q++)
    {
        int X, Y;
        cin >> X >> Y;

        if(left_reach[X] <= Y && Y <= right_reach[X])
            cout << "YES\n";
        else
            cout << "NO\n";
    }
}

Compilation message (stderr)

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:177:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  177 |             if(ind + (1 << bit) >= key_pos_list[ C[i-1] ].size()) continue;
      |                ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
long_mansion.cpp:195:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  195 |             if(ind + (1 << bit) >= key_pos_list[ C[i] ].size()) continue;
      |                ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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