Submission #17882

#TimeUsernameProblemLanguageResultExecution timeMemory
17882ElibayWeighting stones (IZhO11_stones)C++14
0 / 100
85 ms11096 KiB
#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 = INF)
    {
        Max = -X;
        Min = X;
        add = 0;
    } 
} t[MaxN];
void push (int v)
{
    if (t[v].add)
    {
        t[v].Max += t[v].add;
        t[v].Min += t[v].add;
        t[v + v].add += t[v].add;
        t[v + v + 1].add += t[v].add;
    }
}
void build (int v, int l, int r)
{
    if (l == r)
        t[v].Max = 0, t[v].Min = 0;
    else
    {
        int m = (l + r) >> 1;
        build (v + v, l, m);
        build (v + v + 1, m + 1, r);
        t[v].Max = 0;
        t[v].Min = 0;
    }
}
void upd (int v, int l, int r, int L, int R, int val)
{
    push (v);
    if (l > R || r < L)
        return;
    if (L <= l && r <= R)
    {
        t[v].add = val;
        push (v);
        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);
    build (1, 1, n);
    for (int i = 1; i <= n; ++ 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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...