oj.uz

Submission #988723

# Submission time Handle Problem Language Result Execution time Memory
988723 2024-05-25T17:42:51 Z canadavid1 Alternating Heights (CCO22_day1problem1) C++17
4 / 25
 664 ms 15892 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;
    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 (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 262 ms 5744 KB Output is correct
2 Correct 259 ms 14968 KB Output is correct
3 Correct 267 ms 14976 KB Output is correct
4 Correct 124 ms 9556 KB Output is correct
5 Correct 147 ms 11584 KB Output is correct
6 Correct 270 ms 14816 KB Output is correct
7 Correct 266 ms 15080 KB Output is correct
8 Correct 263 ms 15088 KB Output is correct
9 Correct 290 ms 15136 KB Output is correct
10 Correct 435 ms 15440 KB Output is correct
11 Correct 664 ms 15892 KB Output is correct
12 Correct 651 ms 15184 KB Output is correct

Subtask #2
0 / 6.0

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

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2808 KB Output is correct
2 Runtime error 263 ms 5004 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 5744 KB Output is correct
2 Correct 259 ms 14968 KB Output is correct
3 Correct 267 ms 14976 KB Output is correct
4 Correct 124 ms 9556 KB Output is correct
5 Correct 147 ms 11584 KB Output is correct
6 Correct 270 ms 14816 KB Output is correct
7 Correct 266 ms 15080 KB Output is correct
8 Correct 263 ms 15088 KB Output is correct
9 Correct 290 ms 15136 KB Output is correct
10 Correct 435 ms 15440 KB Output is correct
11 Correct 664 ms 15892 KB Output is correct
12 Correct 651 ms 15184 KB Output is correct
13 Incorrect 158 ms 5716 KB Output isn't correct
14 Halted 0 ms 0 KB -