Submission #517262

#	Time	Username	Problem	Language	Result	Execution time	Memory
517262		Be_dos	Weighting stones (IZhO11_stones)	C++17	100 / 100	307 ms	5988 KiB

stones

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

std::pair<int32_t, int32_t>* segtree;
int32_t* lazy;

void propagate(int32_t node) {
    segtree[node * 2 + 1].first += lazy[node];
    segtree[node * 2 + 1].second += lazy[node];
    lazy[node * 2 + 1] += lazy[node];
    segtree[node * 2 + 2].first += lazy[node];
    segtree[node * 2 + 2].second += lazy[node];
    lazy[node * 2 + 2] += lazy[node];
    lazy[node] = 0;
}

void add(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].first += x;
        segtree[node].second += x;
        lazy[node]+=x;
        return;
    }
    int32_t m = (left + right) / 2;
    propagate(node);
    add(node * 2 + 1, left, m, query_left, query_right, x);
    add(node * 2 + 2, m, right, query_left, query_right, x);
    segtree[node].first = std::min(segtree[node * 2 + 1].first, segtree[node * 2 + 2].first);
    segtree[node].second = std::max(segtree[node * 2 + 1].second, segtree[node * 2 + 2].second);
}

int main() {
    int32_t n;
    std::cin >> n;

    segtree = new std::pair<int32_t, int32_t>[n * 4];
    lazy = new int32_t[n * 4];
    for(int32_t i = 0; i < n * 4; i++) {
        segtree[i] = {0, 0};
        lazy[i] = 0;
    }

    for(int32_t i = 0; i < n; i++) {
        int32_t x, set;
        std::cin >> x >> set;

        if(set == 1) {
            add(0, 0, n, n - x, n, 1);
        } else {
            add(0, 0, n, n - x, n, -1);
        }

        bool can_1 = segtree[0].second > 0;
        bool can_2 = segtree[0].first < 0;
        if(can_1 && can_2)
            std::cout << '?' << "\n";
        else if(can_1)
            std::cout << '>' << "\n";
        else
            std::cout << "<" << "\n";
    }
    return 0;
}

• Subtask 1: 100 / 100