Submission #988731

#TimeUsernameProblemLanguageResultExecution timeMemory
988731canadavid1Alternating Heights (CCO22_day1problem1)C++17
4 / 25
648 ms15840 KiB
#include <iostream> #include <vector> #include <bitset> #include <array> constexpr int MAX_K = 3000; int main() { std::cin.tie(0)->sync_with_stdio(0); // O(N^2 K/w) 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<int> works_max(N); for(int x = 0; x < N; x++) { std::array<std::array<std::bitset<MAX_K>,MAX_K>,2> ltgt; works_max[x] = x; 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; if((ltgt[0][a]&ltgt[1][a]).any() || ltgt[0][a][a] || ltgt[1][a][a]) break; works_max[x] = y; } } for(auto i : works_max) std::cerr << i << "\n"; for (int i = 0; i < Q; i++) { int x,y; std::cin >> x >> y; x--;y--; std::cout << (works_max[x]>=y ? "YES" : "NO") << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...