Submission #880025

#	Time	Username	Problem	Language	Result	Execution time	Memory
880025		heeheeheehaaw	Weighting stones (IZhO11_stones)	C++17	100 / 100	172 ms	6436 KiB

stones

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