oj.uz

Submission #334060

# Submission time Handle Problem Language Result Execution time Memory
334060 2020-12-08T08:48:02 Z iulia13 Weighting stones (IZhO11_stones) C++14
100 / 100
 348 ms 4480 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
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 3 ms 364 KB Output is correct
8 Correct 4 ms 364 KB Output is correct
9 Correct 4 ms 364 KB Output is correct
10 Correct 29 ms 768 KB Output is correct
11 Correct 198 ms 2412 KB Output is correct
12 Correct 331 ms 4424 KB Output is correct
13 Correct 344 ms 4460 KB Output is correct
14 Correct 346 ms 4460 KB Output is correct
15 Correct 345 ms 4460 KB Output is correct
16 Correct 344 ms 4332 KB Output is correct
17 Correct 348 ms 4460 KB Output is correct
18 Correct 348 ms 4332 KB Output is correct
19 Correct 345 ms 4332 KB Output is correct
20 Correct 339 ms 4460 KB Output is correct
21 Correct 342 ms 4460 KB Output is correct
22 Correct 344 ms 4332 KB Output is correct
23 Correct 348 ms 4480 KB Output is correct
24 Correct 344 ms 4332 KB Output is correct
25 Correct 342 ms 4460 KB Output is correct