Submission #988739

#	Time	Username	Problem	Language	Result	Execution time	Memory
988739		canadavid1	Alternating Heights (CCO22_day1problem1)	C++17	0 / 25	190 ms	20684 KiB

Main

#include <iostream>
#include <vector>
#include <bitset>
#include <array>
#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;
        if(x > 0) l = works_max[x-1];
        int r = N;
        std::vector<std::vector<int>> reach[2] = {std::vector<std::vector<int>>(K),std::vector<std::vector<int>>(K)};
        bool p = 1;
        while(r-l>1) // logN repetitions
        {
            int m = (r+l)/2;
            if(p)
                for(int i = l+1; i <= m; i++)
                {
                    reach[i%2][A[i]].push_back(A[i-1]); // O(N) total
                    reach[!(i%2)][A[i-1]].push_back(A[i]);
                }
            else
                for(int i = m+1; i<=r; i++)
                {
                    reach[i%2][A[i]].pop_back();
                    reach[!(i%2)][A[i-1]].pop_back();
                }
            
            bool b = 1;
            auto& g = reach[0];
            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();
                seen[n] = true;
                for(auto ne : g[n])
                {
                    inct[ne]--;
                    if(!inct[ne]) S.push_back(ne);
                }
            }
            for(auto i : seen) 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: 0 / 4
• Subtask 2: 0 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 8