oj.uz

Submission #879533

# Submission time Handle Problem Language Result Execution time Memory
879533 2023-11-27T15:37:29 Z alexdd Weighting stones (IZhO11_stones) C++17
100 / 100
 182 ms 4604 KB 
#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int n;
pair<int,int> aint[270000];
int lazy[270000];
pair<int,int> combine(pair<int,int> x, pair<int,int> y)
{
    return {min(x.first,y.first), max(x.second,y.second)};
}
void propagate(int nod)
{
    lazy[nod*2]+=lazy[nod];
    lazy[nod*2+1]+=lazy[nod];
    aint[nod*2].first+=lazy[nod];
    aint[nod*2].second+=lazy[nod];
    aint[nod*2+1].first+=lazy[nod];
    aint[nod*2+1].second+=lazy[nod];
    lazy[nod]=0;
}
void upd(int nod, int st, int dr, int le, int ri, int newv)
{
    if(le>ri)
        return;
    if(le==st && dr==ri)
    {
        aint[nod].first += newv;
        aint[nod].second += newv;
        lazy[nod] += newv;
        return;
    }
    propagate(nod);
    int mij=(st+dr)/2;
    upd(nod*2,st,mij,le,min(mij,ri),newv);
    upd(nod*2+1,mij+1,dr,max(mij+1,le),ri,newv);
    aint[nod] = combine(aint[nod*2], aint[nod*2+1]);
}
signed main()
{
    cin>>n;
    int r,s;
    for(int i=1;i<=n;i++)
    {
        cin>>r>>s;
        if(s==1)
        {
            upd(1,1,n,1,r,-1);
        }
        else
        {
            upd(1,1,n,1,r,1);
        }
        if(aint[1].first<0 && aint[1].second>0)
        {
            cout<<"?\n";
        }
        else if(aint[1].first<0)
            cout<<">\n";
        else
            cout<<"<\n";
    }
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 2 ms 2396 KB Output is correct
8 Correct 3 ms 2396 KB Output is correct
9 Correct 2 ms 2396 KB Output is correct
10 Correct 15 ms 2668 KB Output is correct
11 Correct 91 ms 3184 KB Output is correct
12 Correct 158 ms 4604 KB Output is correct
13 Correct 160 ms 4348 KB Output is correct
14 Correct 161 ms 4340 KB Output is correct
15 Correct 161 ms 4320 KB Output is correct
16 Correct 174 ms 4432 KB Output is correct
17 Correct 159 ms 4260 KB Output is correct
18 Correct 182 ms 4488 KB Output is correct
19 Correct 162 ms 4416 KB Output is correct
20 Correct 159 ms 4336 KB Output is correct
21 Correct 161 ms 4428 KB Output is correct
22 Correct 165 ms 4320 KB Output is correct
23 Correct 159 ms 4484 KB Output is correct
24 Correct 164 ms 4436 KB Output is correct
25 Correct 161 ms 4436 KB Output is correct