Submission #515662

#	Time	Username	Problem	Language	Result	Execution time	Memory
515662		Be_dos	Trading (IZhO13_trading)	C++17	100 / 100	192 ms	12600 KiB

trading

#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 / 100