oj.uz

Submission #8838

# Submission time Handle Problem Language Result Execution time Memory
8838 2014-09-21T08:25:36 Z baneling100 Weighting stones (IZhO11_stones) C++
100 / 100
 64 ms 4156 KB 
#include <stdio.h>
#include <algorithm>

using namespace std;

int N, R, S, M, Value, Max[262144], Min[262144], Idx[262144];

void SegTree(int Left, int Right, int Loc) {

    int Mid = (Left + Right) / 2;

    if(Right <= R) {
        Max[Loc] += Value;
        Min[Loc] += Value;
        Idx[Loc] += Value;
    }
    else {
        Max[2 * Loc] += Idx[Loc];
        Min[2 * Loc] += Idx[Loc];
        Idx[2 * Loc] += Idx[Loc];
        Max[2 * Loc + 1] += Idx[Loc];
        Min[2 * Loc + 1] += Idx[Loc];
        Idx[2 * Loc + 1] += Idx[Loc];
        Idx[Loc] = 0;
        SegTree(Left, Mid, 2 * Loc);
        if(Mid + 1 <= R)
            SegTree(Mid + 1, Right, 2 * Loc + 1);
        Max[Loc] = max(Max[2 * Loc], Max[2 * Loc + 1]);
        Min[Loc] = min(Min[2 * Loc], Min[2 * Loc + 1]);
    }
}

int main(void) {

    int i;

    scanf("%d", &N);
    for(M = 1 ; M < N ; M *= 2);
    for(i = 1 ; i <= N ; i++) {
        scanf("%d %d", &R, &S);
        if(S == 1)
            Value = 1;
        else
            Value = -1;
        SegTree(1, M, 1);
        if(Min[1] >= 0)
            printf(">\n");
        else if(Max[1] <= 0)
            printf("<\n");
        else
            printf("?\n");
    }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4156 KB Output is correct - 73 tokens
2 Correct 0 ms 4156 KB Output is correct - 89 tokens
3 Correct 0 ms 4156 KB Output is correct - 221 tokens
4 Correct 0 ms 4156 KB Output is correct - 21 tokens
5 Correct 0 ms 4156 KB Output is correct - 369 tokens
6 Correct 0 ms 4156 KB Output is correct - 492 tokens
7 Correct 0 ms 4156 KB Output is correct - 945 tokens
8 Correct 0 ms 4156 KB Output is correct - 1237 tokens
9 Correct 0 ms 4156 KB Output is correct - 1105 tokens
10 Correct 6 ms 4156 KB Output is correct - 8921 tokens
11 Correct 29 ms 4156 KB Output is correct - 56110 tokens
12 Correct 59 ms 4156 KB Output is correct - 90207 tokens
13 Correct 57 ms 4156 KB Output is correct - 100000 tokens
14 Correct 62 ms 4156 KB Output is correct - 100000 tokens
15 Correct 61 ms 4156 KB Output is correct - 100000 tokens
16 Correct 62 ms 4156 KB Output is correct - 100000 tokens
17 Correct 64 ms 4156 KB Output is correct - 100000 tokens
18 Correct 60 ms 4156 KB Output is correct - 99999 tokens
19 Correct 53 ms 4156 KB Output is correct - 99999 tokens
20 Correct 60 ms 4156 KB Output is correct - 99999 tokens
21 Correct 64 ms 4156 KB Output is correct - 100000 tokens
22 Correct 54 ms 4156 KB Output is correct - 100000 tokens
23 Correct 58 ms 4156 KB Output is correct - 100000 tokens
24 Correct 60 ms 4156 KB Output is correct - 100000 tokens
25 Correct 60 ms 4156 KB Output is correct - 100000 tokens