oj.uz

Submission #17891

# Submission time Handle Problem Language Result Execution time Memory
17891 2016-01-13T05:53:27 Z Elibay Weighting stones (IZhO11_stones) C++14
100 / 100
 81 ms 11096 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 11096 KB Output is correct - 73 tokens
2 Correct 0 ms 11096 KB Output is correct - 89 tokens
3 Correct 0 ms 11096 KB Output is correct - 221 tokens
4 Correct 0 ms 11096 KB Output is correct - 21 tokens
5 Correct 0 ms 11096 KB Output is correct - 369 tokens
6 Correct 0 ms 11096 KB Output is correct - 492 tokens
7 Correct 0 ms 11096 KB Output is correct - 945 tokens
8 Correct 0 ms 11096 KB Output is correct - 1237 tokens
9 Correct 0 ms 11096 KB Output is correct - 1105 tokens
10 Correct 6 ms 11096 KB Output is correct - 8921 tokens
11 Correct 42 ms 11096 KB Output is correct - 56110 tokens
12 Correct 79 ms 11096 KB Output is correct - 90207 tokens
13 Correct 68 ms 11096 KB Output is correct - 100000 tokens
14 Correct 78 ms 11096 KB Output is correct - 100000 tokens
15 Correct 74 ms 11096 KB Output is correct - 100000 tokens
16 Correct 61 ms 11096 KB Output is correct - 100000 tokens
17 Correct 65 ms 11096 KB Output is correct - 100000 tokens
18 Correct 81 ms 11096 KB Output is correct - 99999 tokens
19 Correct 77 ms 11096 KB Output is correct - 99999 tokens
20 Correct 74 ms 11096 KB Output is correct - 99999 tokens
21 Correct 69 ms 11096 KB Output is correct - 100000 tokens
22 Correct 75 ms 11096 KB Output is correct - 100000 tokens
23 Correct 73 ms 11096 KB Output is correct - 100000 tokens
24 Correct 78 ms 11096 KB Output is correct - 100000 tokens
25 Correct 66 ms 11096 KB Output is correct - 100000 tokens