oj.uz

Submission #524732

# Submission time Handle Problem Language Result Execution time Memory
524732 2022-02-09T22:11:56 Z TheKingAleks Weighting stones (IZhO11_stones) C++14
100 / 100
 153 ms 4420 KB 
#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 1e6+2;
pair<int,int> tree[MAX_N*4];
int lazy[MAX_N*4];
void update(int node, int tl, int tr, int l, int r, int val)
{
    if(lazy[node])
    {
        tree[node].first += lazy[node];
        tree[node].second += lazy[node];
        if(tl != tr)
        {
            lazy[node*2]+=lazy[node];
            lazy[node*2+1]+=lazy[node];
        }
        lazy[node] = 0;
    }
    if(tl >= l && tr <= r)
    {
        tree[node].first += val;
        tree[node].second += val;
        if(tl != tr)
        {
            lazy[node*2]+=val;
            lazy[node*2+1]+=val;
        }
        return;
    }
    if(tl > r || tr < l) return;
    int mid = (tl+tr)/2;
    update(node*2, tl, mid, l, r, val);
    update(node*2+1, mid+1, tr, l, r, val);
    tree[node].first = max(tree[node*2].first,tree[node*2+1].first);
    tree[node].second = min(tree[node*2].second,tree[node*2+1].second);
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int s;
    cin>>s;
    for(int i=0; i<s; i++)
    {
        int val,flag;
        cin>>val>>flag;
        if(flag == 1)
        {
            update(1,1,100002,1,val,1);
        }
        else
        {
            update(1,1,100002,1,val,-1);
        }
        if(tree[1].first >= 0 && tree[1].second >= 0) cout<<">"<<endl;
        else if(tree[1].first <= 0 && tree[1].second <= 0) cout<<"<"<<endl;
        else cout<<"?"<<endl;

    }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 13 ms 708 KB Output is correct
11 Correct 85 ms 2624 KB Output is correct
12 Correct 136 ms 3904 KB Output is correct
13 Correct 145 ms 4308 KB Output is correct
14 Correct 145 ms 4328 KB Output is correct
15 Correct 153 ms 4420 KB Output is correct
16 Correct 141 ms 4256 KB Output is correct
17 Correct 144 ms 4360 KB Output is correct
18 Correct 144 ms 4296 KB Output is correct
19 Correct 143 ms 4292 KB Output is correct
20 Correct 143 ms 4268 KB Output is correct
21 Correct 142 ms 4296 KB Output is correct
22 Correct 151 ms 4344 KB Output is correct
23 Correct 143 ms 4296 KB Output is correct
24 Correct 146 ms 4296 KB Output is correct
25 Correct 144 ms 4336 KB Output is correct