oj.uz

Submission #988732

# Submission time Handle Problem Language Result Execution time Memory
988732 2024-05-25T19:20:06 Z canadavid1 Alternating Heights (CCO22_day1problem1) C++17
10 / 25
 404 ms 12152 KB 
#include <iostream>
#include <vector>
#include <bitset>
#include <array>
constexpr int MAX_K = 64;
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
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 3412 KB Output is correct
2 Correct 166 ms 3408 KB Output is correct
3 Correct 192 ms 3440 KB Output is correct
4 Correct 118 ms 3232 KB Output is correct
5 Correct 137 ms 3552 KB Output is correct
6 Correct 166 ms 3272 KB Output is correct
7 Correct 161 ms 3328 KB Output is correct
8 Correct 196 ms 3412 KB Output is correct
9 Correct 177 ms 3556 KB Output is correct
10 Correct 287 ms 3924 KB Output is correct
11 Correct 404 ms 4588 KB Output is correct
12 Correct 372 ms 4328 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 3412 KB Output is correct
2 Correct 141 ms 3408 KB Output is correct
3 Correct 155 ms 11096 KB Output is correct
4 Correct 121 ms 8148 KB Output is correct
5 Correct 136 ms 9296 KB Output is correct
6 Correct 146 ms 11092 KB Output is correct
7 Correct 145 ms 10948 KB Output is correct
8 Correct 145 ms 11344 KB Output is correct
9 Correct 151 ms 11332 KB Output is correct
10 Correct 159 ms 12152 KB Output is correct
11 Correct 155 ms 11844 KB Output is correct
12 Correct 1 ms 348 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Runtime error 1 ms 604 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 3412 KB Output is correct
2 Correct 166 ms 3408 KB Output is correct
3 Correct 192 ms 3440 KB Output is correct
4 Correct 118 ms 3232 KB Output is correct
5 Correct 137 ms 3552 KB Output is correct
6 Correct 166 ms 3272 KB Output is correct
7 Correct 161 ms 3328 KB Output is correct
8 Correct 196 ms 3412 KB Output is correct
9 Correct 177 ms 3556 KB Output is correct
10 Correct 287 ms 3924 KB Output is correct
11 Correct 404 ms 4588 KB Output is correct
12 Correct 372 ms 4328 KB Output is correct
13 Correct 143 ms 3412 KB Output is correct
14 Correct 141 ms 3408 KB Output is correct
15 Correct 155 ms 11096 KB Output is correct
16 Correct 121 ms 8148 KB Output is correct
17 Correct 136 ms 9296 KB Output is correct
18 Correct 146 ms 11092 KB Output is correct
19 Correct 145 ms 10948 KB Output is correct
20 Correct 145 ms 11344 KB Output is correct
21 Correct 151 ms 11332 KB Output is correct
22 Correct 159 ms 12152 KB Output is correct
23 Correct 155 ms 11844 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 600 KB Output is correct
26 Runtime error 1 ms 604 KB Execution killed with signal 11
27 Halted 0 ms 0 KB -