oj.uz

Submission #475362

# Submission time Handle Problem Language Result Execution time Memory
475362 2021-09-22T06:41:43 Z SamAnd Weighting stones (IZhO11_stones) C++17
100 / 100
 83 ms 48224 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 47172 KB Output is correct
2 Correct 26 ms 47188 KB Output is correct
3 Correct 26 ms 47180 KB Output is correct
4 Correct 26 ms 47288 KB Output is correct
5 Correct 29 ms 47184 KB Output is correct
6 Correct 27 ms 47292 KB Output is correct
7 Correct 26 ms 47228 KB Output is correct
8 Correct 27 ms 47268 KB Output is correct
9 Correct 27 ms 47188 KB Output is correct
10 Correct 32 ms 47364 KB Output is correct
11 Correct 59 ms 47804 KB Output is correct
12 Correct 83 ms 48068 KB Output is correct
13 Correct 68 ms 48184 KB Output is correct
14 Correct 68 ms 48152 KB Output is correct
15 Correct 72 ms 48188 KB Output is correct
16 Correct 74 ms 48152 KB Output is correct
17 Correct 69 ms 48128 KB Output is correct
18 Correct 73 ms 48196 KB Output is correct
19 Correct 70 ms 48224 KB Output is correct
20 Correct 71 ms 48152 KB Output is correct
21 Correct 70 ms 48192 KB Output is correct
22 Correct 74 ms 48132 KB Output is correct
23 Correct 68 ms 48184 KB Output is correct
24 Correct 72 ms 48148 KB Output is correct
25 Correct 71 ms 48136 KB Output is correct