oj.uz

Submission #474068

# Submission time Handle Problem Language Result Execution time Memory
474068 2021-09-16T18:42:50 Z ogibogi2004 Simple game (IZhO17_game) C++14
100 / 100
 265 ms 6812 KB 
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+6;
const int MAXH=1e6+6;
int fen[MAXH];
void update(int idx,int val)
{
    for(;idx<MAXH;idx+=idx&(-idx))
    {
        fen[idx]+=val;
    }
}
void update_range(int l,int r,int val)
{
    update(l,val);
    update(r+1,-val);
}
int query(int idx)
{
    int ret=0;
    for(;idx>0;idx-=idx&(-idx))
    {
        ret+=fen[idx];
    }
    return ret;
}
int n,m;
int y[MAXN];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>y[i];
    }
    for(int i=2;i<=n;i++)
    {
        int l=y[i-1],r=y[i];
        if(l>r)swap(l,r);
        update_range(l,r,+1);
    }
    for(int i=0;i<m;i++)
    {
        int t;cin>>t;
        if(t==1)
        {
            int pos,val;
            cin>>pos>>val;
            if(pos>1)
            {
                update_range(min(y[pos-1],y[pos]),max(y[pos-1],y[pos]),-1);
                update_range(min(val,y[pos-1]),max(y[pos-1],val),+1);
            }
            if(pos<n)
            {
                update_range(min(y[pos+1],y[pos]),max(y[pos+1],y[pos]),-1);
                update_range(min(val,y[pos+1]),max(y[pos+1],val),+1);
            }
            y[pos]=val;
        }
        else
        {
            int h;
            cin>>h;
            cout<<query(h)<<endl;
        }
    }
return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 4 ms 4044 KB Output is correct
3 Correct 4 ms 4044 KB Output is correct
4 Correct 4 ms 4044 KB Output is correct
5 Correct 4 ms 4044 KB Output is correct
6 Correct 6 ms 4044 KB Output is correct
7 Correct 4 ms 332 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 4 ms 4044 KB Output is correct
3 Correct 4 ms 4044 KB Output is correct
4 Correct 4 ms 4044 KB Output is correct
5 Correct 4 ms 4044 KB Output is correct
6 Correct 6 ms 4044 KB Output is correct
7 Correct 4 ms 332 KB Output is correct
8 Correct 230 ms 1616 KB Output is correct
9 Correct 265 ms 6720 KB Output is correct
10 Correct 264 ms 6812 KB Output is correct
11 Correct 233 ms 1732 KB Output is correct
12 Correct 259 ms 2752 KB Output is correct
13 Correct 257 ms 3084 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 4 ms 4044 KB Output is correct
3 Correct 4 ms 4044 KB Output is correct
4 Correct 4 ms 4044 KB Output is correct
5 Correct 4 ms 4044 KB Output is correct
6 Correct 6 ms 4044 KB Output is correct
7 Correct 4 ms 332 KB Output is correct
8 Correct 230 ms 1616 KB Output is correct
9 Correct 265 ms 6720 KB Output is correct
10 Correct 264 ms 6812 KB Output is correct
11 Correct 233 ms 1732 KB Output is correct
12 Correct 259 ms 2752 KB Output is correct
13 Correct 257 ms 3084 KB Output is correct
14 Correct 214 ms 6728 KB Output is correct
15 Correct 214 ms 6724 KB Output is correct
16 Correct 252 ms 6812 KB Output is correct
17 Correct 228 ms 6744 KB Output is correct
18 Correct 228 ms 6788 KB Output is correct