oj.uz

답안 #334059

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
334059 2020-12-08T08:47:07 Z iulia13 Red-blue table (IZhO19_stones) C++14
0 / 100
 2 ms 384 KB 
#include <iostream>
#include <map>
using namespace std;
struct ura{
    int mini, maxi;
};
ura seg[400005];
int lazy[400005];
void push(int nod)
{
    lazy[2 * nod] += lazy[nod];
    lazy[2 * nod + 1] += lazy[nod];
    seg[2 * nod].maxi += lazy[nod];
    seg[2 * nod].mini += lazy[nod];
    seg[2 * nod + 1].maxi += lazy[nod];
    seg[2 * nod + 1].mini += lazy[nod];
    lazy[nod] = 0;
}
void update(int nod, int l, int r, int ql, int qr, int val)
{
    if (ql <= l && r <= qr)
    {
        seg[nod].maxi += val;
        seg[nod].mini += val;
        lazy[nod] += val;
        return;
    }
    if (l > r || l > qr || r < ql)
        return;
    push(nod);
    int mid = (l + r) / 2;
    update(2 * nod, l, mid, ql, qr, val);
    update(2 * nod + 1, mid + 1, r, ql, qr, val);
    seg[nod].maxi = max(seg[nod * 2].maxi, seg[nod * 2 + 1].maxi);
    seg[nod].mini = min(seg[nod * 2].mini, seg[nod * 2 + 1].mini);
}
int cnt1, cnt2;
void query(int nod, int l, int r)
{
    if (seg[nod].maxi > 0)
        cnt2++;
    if (l == r)
        return;
    int mid = (l + r) / 2;
    push(nod);
    if (seg[nod * 2 + 1].maxi > 0)
        query(nod * 2 + 1, mid + 1, r);
    else
        query(nod * 2, l, mid);
}
void query2(int nod, int l, int r)
{
    if (seg[nod].mini < 0)
        cnt1++;
    if (l == r)
        return;
    int mid = (l + r) / 2;
    push(nod);
    if (seg[nod * 2 + 1].mini < 0)
        query2(nod * 2 + 1, mid + 1, r);
    else
        query2(nod * 2, l, mid);
}
int main()
{
    int n, i;
    cin >> n;
    for (i = 1 ; i <= n; i++)
    {
        int x, op;
        cin >> x >> op;
        if (op == 2)
            op = -1;
        update(1, 1, n, 1, x, op);
        cnt1 = cnt2 = 0;
        query(1, 1, n);
        query2(1, 1, n);
        if (cnt1 && cnt2)
            cout << "?";
        else
        if (cnt2)
            cout << ">";
        else
            cout << "<";
        cout << endl;
    }
    return 0;
}

Subtask #1
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Expected integer, but ">" found
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 384 KB Expected integer, but ">" found

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Expected integer, but ">" found
2 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 364 KB Expected integer, but ">" found
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Expected integer, but ">" found
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Expected integer, but ">" found
2 Halted 0 ms 0 KB -