Submission #875906

#	Time	Username	Problem	Language	Result	Execution time	Memory
875906		dilanyan	Weighting stones (IZhO11_stones)	C++17	100 / 100	41 ms	7756 KiB

stones

//-------------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 = 200005;

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 (stderr)

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: 100 / 100