Submission #17891

#	Time	Username	Problem	Language	Result	Execution time	Memory
17891		Elibay	Weighting stones (IZhO11_stones)	C++14	100 / 100	81 ms	11096 KiB

stones

#include <bits/stdc++.h>
#define Fname ""
  
using namespace std;
  
const int MaxN = 8e5 + 17, INF = 1e9 + 17, Mod = 1e9 + 7;

int n, x, y;
struct node
{
    int Max;
    int Min;
    int add;
    node (int X = 0)
    {
        Max = -X;
        Min = X;
        add = 0;
    } 
} t[MaxN];
void push (int v, int l, int r)
{
    if (t[v].add)
    {
        t[v].Max += t[v].add;
        t[v].Min += t[v].add;
        if (l != r)
        {
            t[v + v].add += t[v].add;
            t[v + v + 1].add += t[v].add;
        }
        t[v].add = 0;
    }
}
void upd (int v, int l, int r, int L, int R, int val)
{
    push (v, l, r);
    if (l > R || r < L)
        return;
    if (L <= l && r <= R)
    {
        t[v].add = val;
        push (v, l, r);
        return;
    }
    int m = (l + r) >> 1;
    upd (v + v,     l,     m, L, R, val);
    upd (v + v + 1, m + 1, r, L, R, val);
    t[v].Max = max (t[v + v].Max, t[v + v + 1].Max);
    t[v].Min = min (t[v + v].Min, t[v + v + 1].Min);
} 
int main ()
{
    #ifdef Elibay
        freopen (".in", "r", stdin);
    #endif
    scanf ("%d", &n);
    int w = 1;
    while (w < n)
        w *= 2;
    swap (w, n);
    for (int i = 1; i <= w; ++ i)
    {
        scanf ("%d%d", &x, &y);
        int Mx = t[1].Max;
        int My = t[1].Min;
        if (y == 2)
            upd (1, 1, n, 1, x, -1);
        else
            upd (1, 1, n, 1, x, 1);
        Mx = t[1].Max;
        My = t[1].Min;
        if (Mx > 0 && My >= 0)
            puts (">");
        else if (Mx <= 0 && My < 0)
            puts ("<");
        else
            puts ("?");
    }
    return 0;
}

• Subtask 1: 100 / 100