Submission #475362

#	Time	Username	Problem	Language	Result	Execution time	Memory
475362		SamAnd	Weighting stones (IZhO11_stones)	C++17	100 / 100	83 ms	48224 KiB

stones

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 1000006;

struct ban
{
    int s, minu, maxu;
    ban()
    {
        s = minu = maxu = 0;
    }
    ban(int x)
    {
        s = x;
        minu = min(0, x);
        maxu = max(0, x);
    }
};

ban mer(const ban& l, const ban& r)
{
    ban res;
    res.s = l.s + r.s;
    res.minu = min(r.minu, r.s + l.minu);
    res.maxu = max(r.maxu, r.s + l.maxu);
    return res;
}

ban t[N * 4];

void ubd(int tl, int tr, int x, int y, int pos)
{
    if (tl == tr)
    {
        t[pos] = ban(y);
        return;
    }
    int m = (tl + tr) / 2;
    if (x <= m)
        ubd(tl, m, x, y, pos * 2);
    else
        ubd(m + 1, tr, x, y, pos * 2 + 1);
    t[pos] = mer(t[pos * 2], t[pos * 2 + 1]);
}

int n;

void solv()
{
    cin >> n;

    for (int i = 1; i <= n; ++i)
    {
        int x, ty;
        cin >> x >> ty;
        if (ty == 1)
            ubd(1, n, x, 1, 1);
        else
            ubd(1, n, x, -1, 1);

        if (t[1].minu >= 0)
            cout << ">\n";
        else if (t[1].maxu <= 0)
            cout << "<\n";
        else
            cout << "?\n";
    }
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    ios_base::sync_with_stdio(false), cin.tie(0);

    int tt = 1;
    //cin >> tt;
    while (tt--)
        solv();
    return 0;
}

• Subtask 1: 100 / 100