# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
875902 | dilanyan | Weighting stones (IZhO11_stones) | C++17 | 19 ms | 9052 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//-------------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 (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |