oj.uz

Submission #880025

# Submission time Handle Problem Language Result Execution time Memory
880025 2023-11-28T15:22:59 Z heeheeheehaaw Weighting stones (IZhO11_stones) C++17
100 / 100
 172 ms 6436 KB 
#include <bits/stdc++.h>

using namespace std;

struct node
{
    int mxm, mnm;
};

node combine(node a, node b)
{
    node rez = a;
    rez.mxm = max(rez.mxm, b.mxm);
    rez.mnm = min(rez.mnm, b.mnm);
    return rez;
}

node aint[400005];
int lazy[400005];
const int INF = 1e9;

void propagate(int nod)
{
    aint[nod * 2].mxm += lazy[nod];
    aint[nod * 2].mnm += lazy[nod];
    aint[nod * 2 + 1].mxm += lazy[nod];
    aint[nod * 2 + 1].mnm += lazy[nod];
    lazy[nod * 2] += lazy[nod];
    lazy[nod * 2 + 1] += lazy[nod];
    lazy[nod] = 0;
}

void update(int nod, int st, int dr, int le, int ri, int val)
{
    if(le > ri)
        return;
    if(st == le && dr == ri)
    {
        aint[nod].mnm += val;
        aint[nod].mxm += val;
        lazy[nod] += val;
        return;
    }

    int mij = (st + dr) / 2;
    propagate(nod);
    update(nod * 2, st, mij, le, min(ri, mij), val);
    update(nod * 2 + 1, mij + 1, dr, max(le, mij + 1), ri, val);
    aint[nod] = combine(aint[nod * 2], aint[nod * 2 + 1]);
}

node query(int nod, int st, int dr, int le, int ri)
{
    if(le > ri)
        return {-INF, INF};
    if(st == le && dr == ri)
        return aint[nod];
    int mij = (st + dr) / 2;
    return combine(query(nod * 2, st, mij, le, min(ri, mij)),
                   query(nod * 2 + 1, mij + 1, dr, max(le, mij + 1), ri));
}

int main()
{
    int n;
    cin>>n;
    for(int i = 1; i <= n; i++)
    {
        int a, b;
        cin>>a>>b;
        node rez;
        if(b == 1)
        {
            update(1, 1, n, 1, a, 1);
            rez = query(1, 1, n, 1, n);
        }
        else
        {
            update(1, 1, n, 1, a, -1);
            rez = query(1, 1, n, 1, n);
        }

        rez.mxm = -rez.mxm;
        if(rez.mnm < 0 && rez.mxm >= 0)
            cout<<"<\n";
        else if(rez.mnm >= 0 && rez.mxm < 0)
            cout<<">\n";
        else
            cout<<"?\n";
    }
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2500 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2548 KB Output is correct
7 Correct 2 ms 2492 KB Output is correct
8 Correct 3 ms 2396 KB Output is correct
9 Correct 2 ms 2396 KB Output is correct
10 Correct 17 ms 2652 KB Output is correct
11 Correct 103 ms 5324 KB Output is correct
12 Correct 147 ms 5460 KB Output is correct
13 Correct 162 ms 5468 KB Output is correct
14 Correct 162 ms 5808 KB Output is correct
15 Correct 161 ms 5512 KB Output is correct
16 Correct 164 ms 5764 KB Output is correct
17 Correct 159 ms 5504 KB Output is correct
18 Correct 161 ms 5456 KB Output is correct
19 Correct 160 ms 5636 KB Output is correct
20 Correct 161 ms 5592 KB Output is correct
21 Correct 163 ms 5884 KB Output is correct
22 Correct 160 ms 5456 KB Output is correct
23 Correct 164 ms 5500 KB Output is correct
24 Correct 167 ms 6436 KB Output is correct
25 Correct 172 ms 5604 KB Output is correct