oj.uz

Submission #988848

# Submission time Handle Problem Language Result Execution time Memory
988848 2024-05-26T12:59:23 Z canadavid1 Alternating Heights (CCO22_day1problem1) C++17
4 / 25
 166 ms 21584 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++)
    {
        std::vector<std::vector<int>> reach(K);
        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;
            if(p)
                for(int i = l+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]);
                }
            else
                for(int i = m+1; i<=r; i++)
                {
                    if(!(i%2)) reach[A[i]].pop_back();
                    else reach[A[i-1]].pop_back();
                }
            
            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";
    }
    

}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 20560 KB Output is correct
2 Correct 124 ms 20560 KB Output is correct
3 Correct 126 ms 20568 KB Output is correct
4 Correct 97 ms 15012 KB Output is correct
5 Correct 106 ms 17236 KB Output is correct
6 Correct 166 ms 20700 KB Output is correct
7 Correct 127 ms 20564 KB Output is correct
8 Correct 142 ms 20816 KB Output is correct
9 Correct 131 ms 20820 KB Output is correct
10 Correct 135 ms 21196 KB Output is correct
11 Correct 132 ms 21584 KB Output is correct
12 Correct 125 ms 21076 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 113 ms 19140 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 62 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 20560 KB Output is correct
2 Correct 124 ms 20560 KB Output is correct
3 Correct 126 ms 20568 KB Output is correct
4 Correct 97 ms 15012 KB Output is correct
5 Correct 106 ms 17236 KB Output is correct
6 Correct 166 ms 20700 KB Output is correct
7 Correct 127 ms 20564 KB Output is correct
8 Correct 142 ms 20816 KB Output is correct
9 Correct 131 ms 20820 KB Output is correct
10 Correct 135 ms 21196 KB Output is correct
11 Correct 132 ms 21584 KB Output is correct
12 Correct 125 ms 21076 KB Output is correct
13 Incorrect 113 ms 19140 KB Output isn't correct
14 Halted 0 ms 0 KB -