oj.uz

Submission #515662

# Submission time Handle Problem Language Result Execution time Memory
515662 2022-01-19T12:38:48 Z Be_dos Trading (IZhO13_trading) C++17
100 / 100
 192 ms 12600 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>

int32_t* segtree;

void max_eq(int32_t node, int32_t left, int32_t right, int32_t query_left, int32_t query_right, int32_t x) {
    if(left >= query_right || right <= query_left)
        return;
    if(left >= query_left && right <= query_right) {
        segtree[node] = std::max(segtree[node], x);
        return;
    }
    int32_t m = (left + right) / 2;
    max_eq(node * 2 + 1, left, m, query_left, query_right, x);
    max_eq(node * 2 + 2, m, right, query_left, query_right, x);
}

void ans(int32_t node, int32_t left, int32_t right, int32_t cur_top) {
    cur_top = std::max(cur_top, segtree[node]);
    if(right - left == 1) {
        std::cout << (cur_top == INT32_MIN ? 0 : left + cur_top) << " ";
        return;
    }
    int32_t m = (left + right) / 2;
    ans(node * 2 + 1, left, m, cur_top);
    ans(node * 2 + 2, m, right, cur_top);
}

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

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

    segtree = new int32_t[4 * n];
    for(int32_t i = 0; i < 4 * n; i++)
        segtree[i] = INT32_MIN;

    for(int32_t i = 0; i < num_q; i++) {
        int32_t left, right, x;
        std::cin >> left >> right >> x;
        left--;
        right--;

        max_eq(0, 0, n, left, right + 1, x - left);
    }

    ans(0, 0, n, INT32_MIN);
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 360 KB Output is correct
6 Correct 2 ms 320 KB Output is correct
7 Correct 85 ms 6348 KB Output is correct
8 Correct 107 ms 7236 KB Output is correct
9 Correct 105 ms 7364 KB Output is correct
10 Correct 123 ms 7640 KB Output is correct
11 Correct 112 ms 8660 KB Output is correct
12 Correct 141 ms 8864 KB Output is correct
13 Correct 128 ms 9392 KB Output is correct
14 Correct 138 ms 9372 KB Output is correct
15 Correct 157 ms 10340 KB Output is correct
16 Correct 167 ms 10528 KB Output is correct
17 Correct 148 ms 10708 KB Output is correct
18 Correct 153 ms 11320 KB Output is correct
19 Correct 182 ms 11148 KB Output is correct
20 Correct 192 ms 12600 KB Output is correct