Submission #334060

#	Time	Username	Problem	Language	Result	Execution time	Memory
334060		iulia13	Weighting stones (IZhO11_stones)	C++14	100 / 100	348 ms	4480 KiB

stones

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