oj.uz

Submission #447757

# Submission time Handle Problem Language Result Execution time Memory
447757 2021-07-27T13:14:36 Z blue Long Mansion (JOI17_long_mansion) C++17
100 / 100
 1871 ms 144964 KB 
#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 if(queryAdj(i+1, i) == 1) //i is in the middle of LC
        // {
        //     if(queryAdj(i, i+1) == 1)
        //     {
        //         //compute i+1, then solve for this
        //         tmp.push_back(i);
        //     }
        //     else
        //     {
        //         left_reach[i] = go_left[i];
        //
        //         for(int t: tmp) left_reach[t] = left_reach[i];
        //         tmp.clear();
        //     }
        // }
        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 if(queryAdj(i-1, i) == 1)
        {
            if(queryAdj(i, i-1) == 1)
            {
                tmp.push_back(i);
            }
            else
            {
                right_reach[i] = go_right[i];

                for(int t: tmp) right_reach[t] = right_reach[i];
                tmp.clear();
            }
        }
        else
        {
            int curr_go_left = go_left[i];

            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;
            }

            // 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(right_key_pos[ right_wall.top() ] >= curr_go_left)
            {
                right_wall.pop();
                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;
                }

                // cerr << right_wall.top() << ' ' << right_key_pos[ right_wall.top() ] << ' ' << curr_go_left << '\n';
            }


            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

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

# Verdict Execution time Memory Grader output
1 Correct 18 ms 26316 KB Output is correct
2 Correct 20 ms 26552 KB Output is correct
3 Correct 21 ms 27000 KB Output is correct
4 Correct 19 ms 26312 KB Output is correct
5 Correct 16 ms 26316 KB Output is correct
6 Correct 18 ms 26292 KB Output is correct
7 Correct 18 ms 26312 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 26316 KB Output is correct
2 Correct 20 ms 26552 KB Output is correct
3 Correct 21 ms 27000 KB Output is correct
4 Correct 19 ms 26312 KB Output is correct
5 Correct 16 ms 26316 KB Output is correct
6 Correct 18 ms 26292 KB Output is correct
7 Correct 18 ms 26312 KB Output is correct
8 Correct 133 ms 29124 KB Output is correct
9 Correct 131 ms 29152 KB Output is correct
10 Correct 133 ms 29508 KB Output is correct
11 Correct 137 ms 30020 KB Output is correct
12 Correct 122 ms 29184 KB Output is correct
13 Correct 135 ms 29332 KB Output is correct
14 Correct 128 ms 29376 KB Output is correct
15 Correct 124 ms 29340 KB Output is correct
16 Correct 119 ms 29636 KB Output is correct
17 Correct 128 ms 29368 KB Output is correct
18 Correct 125 ms 29368 KB Output is correct
19 Correct 165 ms 29368 KB Output is correct
20 Correct 122 ms 29464 KB Output is correct
21 Correct 119 ms 29616 KB Output is correct
22 Correct 131 ms 29444 KB Output is correct
23 Correct 132 ms 29252 KB Output is correct
24 Correct 128 ms 29252 KB Output is correct
25 Correct 130 ms 29228 KB Output is correct
26 Correct 131 ms 29252 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 522 ms 52728 KB Output is correct
2 Correct 523 ms 52460 KB Output is correct
3 Correct 487 ms 52456 KB Output is correct
4 Correct 566 ms 52700 KB Output is correct
5 Correct 567 ms 52612 KB Output is correct
6 Correct 545 ms 51856 KB Output is correct
7 Correct 325 ms 52076 KB Output is correct
8 Correct 299 ms 52116 KB Output is correct
9 Correct 303 ms 52152 KB Output is correct
10 Correct 257 ms 52164 KB Output is correct
11 Correct 264 ms 52188 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 26316 KB Output is correct
2 Correct 20 ms 26552 KB Output is correct
3 Correct 21 ms 27000 KB Output is correct
4 Correct 19 ms 26312 KB Output is correct
5 Correct 16 ms 26316 KB Output is correct
6 Correct 18 ms 26292 KB Output is correct
7 Correct 18 ms 26312 KB Output is correct
8 Correct 133 ms 29124 KB Output is correct
9 Correct 131 ms 29152 KB Output is correct
10 Correct 133 ms 29508 KB Output is correct
11 Correct 137 ms 30020 KB Output is correct
12 Correct 122 ms 29184 KB Output is correct
13 Correct 135 ms 29332 KB Output is correct
14 Correct 128 ms 29376 KB Output is correct
15 Correct 124 ms 29340 KB Output is correct
16 Correct 119 ms 29636 KB Output is correct
17 Correct 128 ms 29368 KB Output is correct
18 Correct 125 ms 29368 KB Output is correct
19 Correct 165 ms 29368 KB Output is correct
20 Correct 122 ms 29464 KB Output is correct
21 Correct 119 ms 29616 KB Output is correct
22 Correct 131 ms 29444 KB Output is correct
23 Correct 132 ms 29252 KB Output is correct
24 Correct 128 ms 29252 KB Output is correct
25 Correct 130 ms 29228 KB Output is correct
26 Correct 131 ms 29252 KB Output is correct
27 Correct 522 ms 52728 KB Output is correct
28 Correct 523 ms 52460 KB Output is correct
29 Correct 487 ms 52456 KB Output is correct
30 Correct 566 ms 52700 KB Output is correct
31 Correct 567 ms 52612 KB Output is correct
32 Correct 545 ms 51856 KB Output is correct
33 Correct 325 ms 52076 KB Output is correct
34 Correct 299 ms 52116 KB Output is correct
35 Correct 303 ms 52152 KB Output is correct
36 Correct 257 ms 52164 KB Output is correct
37 Correct 264 ms 52188 KB Output is correct
38 Correct 582 ms 122060 KB Output is correct
39 Correct 673 ms 144964 KB Output is correct
40 Correct 493 ms 99664 KB Output is correct
41 Correct 1405 ms 140576 KB Output is correct
42 Correct 542 ms 52020 KB Output is correct
43 Correct 517 ms 51780 KB Output is correct
44 Correct 1026 ms 75032 KB Output is correct
45 Correct 994 ms 74936 KB Output is correct
46 Correct 980 ms 74816 KB Output is correct
47 Correct 498 ms 52084 KB Output is correct
48 Correct 445 ms 52044 KB Output is correct
49 Correct 940 ms 74876 KB Output is correct
50 Correct 932 ms 75176 KB Output is correct
51 Correct 1008 ms 75044 KB Output is correct
52 Correct 911 ms 74332 KB Output is correct
53 Correct 1384 ms 97276 KB Output is correct
54 Correct 1871 ms 119384 KB Output is correct
55 Correct 1420 ms 103132 KB Output is correct