oj.uz

Submission #988733

# Submission time Handle Problem Language Result Execution time Memory
988733 2024-05-25T19:20:50 Z canadavid1 Alternating Heights (CCO22_day1problem1) C++17
6 / 25
 1000 ms 6736 KB 
#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;
            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 (int i = 0; i < Q; i++)
    {
        int x,y;
        std::cin >> x >> y;
        x--;y--;
        std::cout << (works_max[x]>=y ? "YES" : "NO") << "\n";
    }
    

}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 5460 KB Output is correct
2 Correct 292 ms 5696 KB Output is correct
3 Correct 295 ms 5460 KB Output is correct
4 Correct 131 ms 5544 KB Output is correct
5 Correct 136 ms 5712 KB Output is correct
6 Correct 296 ms 5460 KB Output is correct
7 Correct 329 ms 5488 KB Output is correct
8 Correct 413 ms 5480 KB Output is correct
9 Execution timed out 1067 ms 3940 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 5712 KB Output is correct
2 Correct 169 ms 5712 KB Output is correct
3 Correct 163 ms 5464 KB Output is correct
4 Correct 130 ms 6592 KB Output is correct
5 Correct 136 ms 5856 KB Output is correct
6 Correct 165 ms 5712 KB Output is correct
7 Correct 171 ms 5712 KB Output is correct
8 Correct 175 ms 5712 KB Output is correct
9 Correct 264 ms 5968 KB Output is correct
10 Correct 484 ms 6480 KB Output is correct
11 Correct 484 ms 6736 KB Output is correct
12 Correct 2 ms 2648 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Execution timed out 1082 ms 2652 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 5460 KB Output is correct
2 Correct 292 ms 5696 KB Output is correct
3 Correct 295 ms 5460 KB Output is correct
4 Correct 131 ms 5544 KB Output is correct
5 Correct 136 ms 5712 KB Output is correct
6 Correct 296 ms 5460 KB Output is correct
7 Correct 329 ms 5488 KB Output is correct
8 Correct 413 ms 5480 KB Output is correct
9 Execution timed out 1067 ms 3940 KB Time limit exceeded
10 Halted 0 ms 0 KB -