oj.uz

Submission #519307

# Submission time Handle Problem Language Result Execution time Memory
519307 2022-01-26T07:40:56 Z Be_dos Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
17 / 100
 3000 ms 61260 KB 
#include <iostream>
#include <cmath>
#include <cctype>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <deque>
#include <stack>
#include <unordered_set>
#include <sstream>
#include <cstring>
#include <iomanip>
#include <queue>
#include <unordered_map>
#include <random>
#include <cfloat>
#include <chrono>
#include <bitset>
#include <complex>
#include <immintrin.h>
#include <cassert>

struct Query {
    int32_t left, x;
    int32_t ind;

    Query(int32_t left_, int32_t x_, int32_t ind_) {
        left = left_;
        x = x_;
        ind = ind_;
    }
};

struct Segtree {
    int32_t* arr, *arr2;

    Segtree(int32_t n, int32_t* arr_) {
        arr = arr_;
        arr2 = new int32_t[n];
        for(int32_t i = 0; i < n; i++)
            arr2[i] = -1'000'000'005;
    }

    void max_eq(int32_t left, int32_t right, int32_t x) {
        for(int32_t i = left; i < right; i++)
            arr2[i] = std::max(arr2[i], x);
    }

    int32_t get(int32_t left, int32_t right) {
        int32_t res = -1'000'000'005;
        for(int32_t i = left; i < right; i++)
            res = std::max(res, arr[i] + arr2[i]);
        return res;
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int32_t n, num_q;
    std::cin >> n >> num_q;

    int32_t* arr = new int32_t[n];
    for(int32_t i = 0; i < n; i++)
        std::cin >> arr[i];

    std::vector<Query>* queries = new std::vector<Query>[n];
    int32_t* bounds = new int32_t[num_q];
    for(int32_t q = 0; q < num_q; q++) {
        int32_t left, right, x;
        std::cin >> left >> right >> x;
        left--;
        right--;
        bounds[q] = x;

        queries[right].emplace_back(left, x, q);
    }

    Segtree tree(n, arr);
    std::stack<int32_t> maximums;
    int32_t* ans = new int32_t[n];
    for(int32_t i = 0; i < n; i++) {
        while(!maximums.empty() && arr[maximums.top()] <= arr[i])
            maximums.pop();
        if(!maximums.empty())
            tree.max_eq(0, maximums.top() + 1, arr[i]);
        maximums.push(i);

        for(int32_t q = 0; q < queries[i].size(); q++)
            ans[queries[i][q].ind] = tree.get(queries[i][q].left, i + 1);
    }

    for(int32_t q = 0; q < num_q; q++)
        std::cout << (ans[q] > bounds[q] ? 0 : 1) << "\n";
    return 0;
}

Compilation message

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:91:30: warning: comparison of integer expressions of different signedness: 'int32_t' {aka 'int'} and 'std::vector<Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         for(int32_t q = 0; q < queries[i].size(); q++)
      |                            ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 16 ms 664 KB Output is correct
13 Correct 16 ms 672 KB Output is correct
14 Correct 20 ms 764 KB Output is correct
15 Correct 24 ms 760 KB Output is correct
16 Correct 22 ms 588 KB Output is correct
17 Correct 17 ms 588 KB Output is correct
18 Correct 26 ms 656 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3057 ms 61260 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3093 ms 6316 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 16 ms 664 KB Output is correct
13 Correct 16 ms 672 KB Output is correct
14 Correct 20 ms 764 KB Output is correct
15 Correct 24 ms 760 KB Output is correct
16 Correct 22 ms 588 KB Output is correct
17 Correct 17 ms 588 KB Output is correct
18 Correct 26 ms 656 KB Output is correct
19 Execution timed out 3011 ms 19028 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 16 ms 664 KB Output is correct
13 Correct 16 ms 672 KB Output is correct
14 Correct 20 ms 764 KB Output is correct
15 Correct 24 ms 760 KB Output is correct
16 Correct 22 ms 588 KB Output is correct
17 Correct 17 ms 588 KB Output is correct
18 Correct 26 ms 656 KB Output is correct
19 Execution timed out 3057 ms 61260 KB Time limit exceeded
20 Halted 0 ms 0 KB -