oj.uz

Submission #988904

# Submission time Handle Problem Language Result Execution time Memory
988904 2024-05-26T15:48:07 Z canadavid1 Alternating Heights (CCO22_day1problem1) C++17
25 / 25
 350 ms 21852 KB 
#include <iostream>
#include <vector>
#include <bitset>
#include <array>
#include <deque>
#include <unordered_set>
// #pragma GCC optimize("O3")
int main()
{
    std::cin.tie(0)->sync_with_stdio(0);
    // O(N^2logN)
    int N,K,Q;
    std::cin >> N >> K >> Q;
    std::vector<int> A(N);
    for(auto& i : A) std::cin >> i;
    for(auto& i : A) i--;

    std::vector<std::pair<int,int>> xy(Q);
    for(auto&[x,y] : xy) std::cin >> x >> y;
    std::unordered_set<int> xs;
    for(auto&[x,y] : xy) {x--,y--;xs.insert(x);}

    std::vector<int> works_max(N);
    for(int x = 0; x < N; x++)
    {
        int l = x>0 ? std::max(x,works_max[x-1]) : 0;
        int r = N;
        bool p = 1;
        while(r-l>1)
        {
            int m = l+1;
            std::vector<std::vector<int>> reach(K);
            for(int i = x+1; i <= m; i++)
            {
                if(!(i%2)) reach[A[i]].push_back(A[i-1]); // O(N) total
                else reach[A[i-1]].push_back(A[i]);
            }
            
            bool b = 1;
            auto& g = reach;
            std::vector<int> inct(K);
            for(auto& i : g)
                for(auto& j : i) inct[j]++; // O(N)
            std::vector<int> S;
            for(int i = 0; i < K; i++) if(!inct[i]) S.push_back(i);
            std::vector<bool> seen(K);
            while(S.size()) // O(N)
            {
                auto n = S.back(); S.pop_back();
                for(auto ne : g[n])
                {
                    inct[ne]--;
                    if(!inct[ne]) S.push_back(ne);
                }
            }
            for(auto i : inct) b &= !i;
            
            if(b) l = m;
            else r = m;
            p = b;
        }
        works_max[x] = l;
        
        // bool g = 1;
        // for(int y = x+1; y < N; y++,g = !g)
        // {
        //     auto a = A[y];
        //     auto p = A[y-1];
        //     ltgt[g][a] |= ltgt[g][p];
        //     ltgt[g][a][p] = true;
        //     for(auto& i : ltgt[g]) if(i[a]) i |= ltgt[g][a]; 
        //     bool b = 0;
        //     for(int i = 0; i < K; i++) if((ltgt[0][i]&ltgt[1][i]).any() || ltgt[0][i][i] || ltgt[1][i][i]) b=1;
        //     if(b) break;
        //     works_max[x] = y;
        // }
    }
    for(auto i : works_max) std::cerr << i << "\n";
    for (auto[x,y] : xy)
    {
        std::cout << (works_max[x]>=y ? "YES" : "NO") << "\n";
    }
    

}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:28:14: warning: variable 'p' set but not used [-Wunused-but-set-variable]
   28 |         bool p = 1;
      |              ^

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 20816 KB Output is correct
2 Correct 141 ms 20820 KB Output is correct
3 Correct 158 ms 20812 KB Output is correct
4 Correct 97 ms 15048 KB Output is correct
5 Correct 106 ms 17236 KB Output is correct
6 Correct 135 ms 20816 KB Output is correct
7 Correct 130 ms 20684 KB Output is correct
8 Correct 130 ms 20816 KB Output is correct
9 Correct 132 ms 20816 KB Output is correct
10 Correct 151 ms 21332 KB Output is correct
11 Correct 147 ms 21848 KB Output is correct
12 Correct 158 ms 21072 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 18900 KB Output is correct
2 Correct 116 ms 18772 KB Output is correct
3 Correct 133 ms 18752 KB Output is correct
4 Correct 97 ms 16080 KB Output is correct
5 Correct 108 ms 17112 KB Output is correct
6 Correct 118 ms 18884 KB Output is correct
7 Correct 121 ms 18768 KB Output is correct
8 Correct 117 ms 18768 KB Output is correct
9 Correct 120 ms 19284 KB Output is correct
10 Correct 120 ms 19664 KB Output is correct
11 Correct 133 ms 19796 KB Output is correct
12 Correct 0 ms 344 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 452 KB Output is correct
2 Correct 194 ms 708 KB Output is correct
3 Correct 213 ms 708 KB Output is correct
4 Correct 13 ms 600 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 128 ms 664 KB Output is correct
8 Correct 204 ms 708 KB Output is correct
9 Correct 299 ms 716 KB Output is correct
10 Correct 165 ms 652 KB Output is correct
11 Correct 227 ms 600 KB Output is correct
12 Correct 153 ms 648 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 20816 KB Output is correct
2 Correct 141 ms 20820 KB Output is correct
3 Correct 158 ms 20812 KB Output is correct
4 Correct 97 ms 15048 KB Output is correct
5 Correct 106 ms 17236 KB Output is correct
6 Correct 135 ms 20816 KB Output is correct
7 Correct 130 ms 20684 KB Output is correct
8 Correct 130 ms 20816 KB Output is correct
9 Correct 132 ms 20816 KB Output is correct
10 Correct 151 ms 21332 KB Output is correct
11 Correct 147 ms 21848 KB Output is correct
12 Correct 158 ms 21072 KB Output is correct
13 Correct 130 ms 18900 KB Output is correct
14 Correct 116 ms 18772 KB Output is correct
15 Correct 133 ms 18752 KB Output is correct
16 Correct 97 ms 16080 KB Output is correct
17 Correct 108 ms 17112 KB Output is correct
18 Correct 118 ms 18884 KB Output is correct
19 Correct 121 ms 18768 KB Output is correct
20 Correct 117 ms 18768 KB Output is correct
21 Correct 120 ms 19284 KB Output is correct
22 Correct 120 ms 19664 KB Output is correct
23 Correct 133 ms 19796 KB Output is correct
24 Correct 0 ms 344 KB Output is correct
25 Correct 0 ms 452 KB Output is correct
26 Correct 194 ms 708 KB Output is correct
27 Correct 213 ms 708 KB Output is correct
28 Correct 13 ms 600 KB Output is correct
29 Correct 1 ms 344 KB Output is correct
30 Correct 1 ms 492 KB Output is correct
31 Correct 128 ms 664 KB Output is correct
32 Correct 204 ms 708 KB Output is correct
33 Correct 299 ms 716 KB Output is correct
34 Correct 165 ms 652 KB Output is correct
35 Correct 227 ms 600 KB Output is correct
36 Correct 153 ms 648 KB Output is correct
37 Correct 337 ms 21584 KB Output is correct
38 Correct 350 ms 21332 KB Output is correct
39 Correct 166 ms 20704 KB Output is correct
40 Correct 103 ms 16212 KB Output is correct
41 Correct 113 ms 17488 KB Output is correct
42 Correct 305 ms 21332 KB Output is correct
43 Correct 349 ms 21692 KB Output is correct
44 Correct 288 ms 21332 KB Output is correct
45 Correct 321 ms 21732 KB Output is correct
46 Correct 318 ms 21852 KB Output is correct
47 Correct 347 ms 21844 KB Output is correct