oj.uz

Submission #988731

# Submission time Handle Problem Language Result Execution time Memory
988731 2024-05-25T19:03:54 Z canadavid1 Alternating Heights (CCO22_day1problem1) C++17
4 / 25
 648 ms 15840 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;
            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";
    }
    

}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 14884 KB Output is correct
2 Correct 268 ms 14980 KB Output is correct
3 Correct 262 ms 15172 KB Output is correct
4 Correct 114 ms 9548 KB Output is correct
5 Correct 131 ms 11552 KB Output is correct
6 Correct 266 ms 14812 KB Output is correct
7 Correct 301 ms 14828 KB Output is correct
8 Correct 273 ms 14964 KB Output is correct
9 Correct 299 ms 15140 KB Output is correct
10 Correct 429 ms 15444 KB Output is correct
11 Correct 648 ms 15840 KB Output is correct
12 Correct 637 ms 15224 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 13420 KB Output is correct
2 Incorrect 156 ms 13136 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

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

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 14884 KB Output is correct
2 Correct 268 ms 14980 KB Output is correct
3 Correct 262 ms 15172 KB Output is correct
4 Correct 114 ms 9548 KB Output is correct
5 Correct 131 ms 11552 KB Output is correct
6 Correct 266 ms 14812 KB Output is correct
7 Correct 301 ms 14828 KB Output is correct
8 Correct 273 ms 14964 KB Output is correct
9 Correct 299 ms 15140 KB Output is correct
10 Correct 429 ms 15444 KB Output is correct
11 Correct 648 ms 15840 KB Output is correct
12 Correct 637 ms 15224 KB Output is correct
13 Correct 157 ms 13420 KB Output is correct
14 Incorrect 156 ms 13136 KB Output isn't correct
15 Halted 0 ms 0 KB -