oj.uz

답안 #517259

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
517259 2022-01-22T19:56:34 Z Be_dos 돌 무게 재기 (IZhO11_stones) C++17
0 / 100
 1 ms 208 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>

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 + 1] += 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
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 208 KB Output isn't correct
2 Halted 0 ms 0 KB -