oj.uz

Submission #875902

# Submission time Handle Problem Language Result Execution time Memory
875902 2023-11-20T17:47:43 Z dilanyan Weighting stones (IZhO11_stones) C++17
0 / 100
 19 ms 9052 KB 
//-------------dilanyan------------\\ 
 
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<stdio.h>
using namespace std;

//------------------KarginDefines--------------------\\ 

#define ll long long
#define pb push_back
#define all(u) (u).begin(), (u).end()
#define pqueue priority_queue
#define upper upper_bound
#define lower lower_bound
#define umap unordered_map
#define uset unordered_set
#define Kargin ios_base::sync_with_stdio(false);cin.tie(NULL);
#define Usaco freopen(".in", "r", stdin); freopen(".out", "w", stdout);


//-------------------KarginConstants------------------\\ 
 
const int mod = 1000000007;
const ll inf = 2e9;

//-------------------KarginCode------------------------\\ 
 
const int N = 100005;

int n;

struct node {
    int max, min, sum;
};

node tree[4 * N];

struct segtree {

    int size = 1;

    void init() {
        while (size < n) size <<= 1;
    }

    void propagate(int x) {
        tree[2 * x + 1].sum += tree[x].sum, tree[2 * x + 2].sum += tree[x].sum;
        tree[2 * x + 1].min += tree[x].sum, tree[2 * x + 2].min += tree[x].sum;
        tree[2 * x + 1].max += tree[x].sum, tree[2 * x + 2].max += tree[x].sum;
        tree[x].sum = 0;
    }

    void set(int r, int k, int x, int lx, int rx) {
        if (lx >= r) return;
        if (rx <= r) {
            tree[x].max += k, tree[x].min += k, tree[x].sum += k;
            propagate(x);
            return;
        }
        int m = (lx + rx) / 2;
        propagate(x);
        set(r, k, 2 * x + 1, lx, m), set(r, k, 2 * x + 2, m, rx);
        tree[x].max = max(tree[2 * x + 1].max, tree[2 * x + 2].max);
        tree[x].min = min(tree[2 * x + 1].min, tree[2 * x + 2].min);
    }

    void set(int r, int k) {
        set(r, k, 0, 0, size);
    }

};

void KarginSolve() {
    cin >> n;
    segtree st;
    st.init();
    for (int i = 0;i < n;i++) {
        int r, s;
        cin >> r >> s;
        st.set(r, (s == 1 ? 1 : -1));
        if (tree[0].min >= 0) cout << ">\n";
        else if (tree[0].max <= 0) cout << "<\n";
        else cout << "?\n";
    }
}

int main() {
    //Usaco
    Kargin;
    int test = 1;
    //cin >> test;
    while (test--) {
        KarginSolve();
    }
    return 0;
}

Compilation message

stones.cpp:1:1: warning: multi-line comment [-Wcomment]
    1 | //-------------dilanyan------------\\
      | ^
stones.cpp:8:1: warning: multi-line comment [-Wcomment]
    8 | //------------------KarginDefines--------------------\\
      | ^
stones.cpp:22:1: warning: multi-line comment [-Wcomment]
   22 | //-------------------KarginConstants------------------\\
      | ^
stones.cpp:27:1: warning: multi-line comment [-Wcomment]
   27 | //-------------------KarginCode------------------------\\
      | ^

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 600 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 3 ms 2652 KB Output is correct
11 Correct 19 ms 5252 KB Output is correct
12 Runtime error 4 ms 9052 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -