oj.uz

Submission #167500

# Submission time Handle Problem Language Result Execution time Memory
167500 2019-12-08T17:49:06 Z Toirov_Sadi Weighting stones (IZhO11_stones) C++17
100 / 100
 332 ms 4616 KB 
#include <bits/stdc++.h>

#define fr first
#define se second

using namespace std;

const long long N = 1e5 + 7;
const long long inf = 1e9 + 7;
const long long mod = 1e9 + 7;

int n;
int mn[4 * N];
int mx[4 * N];
int lazy[4 * N];
void push(int v, int tl, int tr){
    if(tl != tr){
        lazy[v * 2] += lazy[v];
        lazy[v * 2 + 1] += lazy[v];
    }
    mx[v] += lazy[v];
    mn[v] += lazy[v];
    lazy[v] = 0;
}
void upd(int v, int tl, int tr, int l, int r, int x){
    push(v, tl, tr);
    if(l > r){
        return;
    }
    if(tl == l && tr == r){
        lazy[v] += x;
        push(v, tl, tr);
        return;
    }
    int tm = (tl + tr) / 2;
    upd(v * 2, tl, tm, l, min(r, tm), x);
    upd(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, x);
    mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
    mn[v] = min(mn[v * 2], mn[v * 2 + 1]);
}
int main()
{
    /// freopen("input.txt", "r", stdin);
    /// freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio( false );

    cin >> n;
    for(int i = 1; i <= n; i ++){
        int x, t;
        cin >> x >> t;
        if(t == 1){
            upd(1, 1, n, 1, x, 1);
        }
        else{
            upd(1, 1, n, 1, x, -1);
        }
        if(mx[1] >= 0 && mn[1] >= 0){
            cout << ">\n";
        }
        else if(mx[1] <= 0 && mn[1] <= 0){
            cout << "<\n";
        }
        else{
            cout << "?\n";
        }
    }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 6 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 30 ms 760 KB Output is correct
11 Correct 193 ms 2456 KB Output is correct
12 Correct 308 ms 4356 KB Output is correct
13 Correct 328 ms 4508 KB Output is correct
14 Correct 328 ms 4472 KB Output is correct
15 Correct 327 ms 4472 KB Output is correct
16 Correct 328 ms 4344 KB Output is correct
17 Correct 326 ms 4472 KB Output is correct
18 Correct 326 ms 4472 KB Output is correct
19 Correct 332 ms 4344 KB Output is correct
20 Correct 326 ms 4472 KB Output is correct
21 Correct 326 ms 4616 KB Output is correct
22 Correct 328 ms 4380 KB Output is correct
23 Correct 327 ms 4444 KB Output is correct
24 Correct 325 ms 4472 KB Output is correct
25 Correct 330 ms 4376 KB Output is correct