oj.uz

Submission #91228

# Submission time Handle Problem Language Result Execution time Memory
91228 2018-12-26T15:23:11 Z Abelyan Simple game (IZhO17_game) C++17
100 / 100
 296 ms 11080 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pr;

#define fr first
#define sc second
#define FOR(i, a) for (int i = 0; i < (a); i++)
#define F0R(i, a, b) for (int i = (a); i <= (b); i++)
#define FORd(i,a) for (int i = (a)-1; i >= 0; i--)
#define F0Rd(i,a,b) for (int i = (b); i >= (a); i--)
#define trav(a, x) for (auto& a : x)

const int N=1000006;

int lazy[4*N];
int h[N];


void update(int v,int tl,int tr,int l,int r,ll del){
    if (l==INT_MAX || r==INT_MAX || l>r) return;
    if (tl==l && tr==r){
        lazy[v]+=del;
        return;
    }
    int tm=(tl+tr)/2;
    update(v+v,tl,tm,l,min(r,tm),del);
    update(v+v+1,tm+1,tr,max(tm+1,l),r,del);
}

int query(int v,int tl,int tr,int ind){
    if (ind==tl && ind==tr){
        return lazy[v];
    }
    int tm=(tl+tr)/2;
    if (ind<=tm)
        return query(v+v,tl,tm,ind)+lazy[v];
    return query(v+v+1,tm+1,tr,ind)+lazy[v];
}

int main(){
    ios_base::sync_with_stdio(false);
    //freopen("input.txt","r",stdin);
    int n,q;
    cin>>n>>q;
    h[0]=INT_MAX;
    F0R(i,1,n){
        cin>>h[i];
        update(1,0,N-1,min(h[i],h[i-1]),max(h[i],h[i-1]),1);
    }
    h[n+1]=INT_MAX;
    FOR(i,q){
        int type;
        cin>>type;
        if (type==1){
            int ind,hgh;
            cin>>ind>>hgh;
            update(1,0,N-1,min(h[ind],h[ind-1]),max(h[ind],h[ind-1]),-1);
            update(1,0,N-1,min(h[ind],h[ind+1]),max(h[ind],h[ind+1]),-1);
            h[ind]=hgh;
            update(1,0,N-1,min(h[ind],h[ind-1]),max(h[ind],h[ind-1]),1);
            update(1,0,N-1,min(h[ind],h[ind+1]),max(h[ind],h[ind+1]),1);
        }
        else{
            int hg;
            cin>>hg;
            cout<<query(1,0,N-1,hg)<<endl;
        }
    }
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 9 ms 6772 KB Output is correct
3 Correct 9 ms 6772 KB Output is correct
4 Correct 10 ms 6772 KB Output is correct
5 Correct 9 ms 6780 KB Output is correct
6 Correct 10 ms 6780 KB Output is correct
7 Correct 5 ms 6780 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 9 ms 6772 KB Output is correct
3 Correct 9 ms 6772 KB Output is correct
4 Correct 10 ms 6772 KB Output is correct
5 Correct 9 ms 6780 KB Output is correct
6 Correct 10 ms 6780 KB Output is correct
7 Correct 5 ms 6780 KB Output is correct
8 Correct 171 ms 6780 KB Output is correct
9 Correct 254 ms 11080 KB Output is correct
10 Correct 248 ms 11080 KB Output is correct
11 Correct 167 ms 11080 KB Output is correct
12 Correct 203 ms 11080 KB Output is correct
13 Correct 205 ms 11080 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 9 ms 6772 KB Output is correct
3 Correct 9 ms 6772 KB Output is correct
4 Correct 10 ms 6772 KB Output is correct
5 Correct 9 ms 6780 KB Output is correct
6 Correct 10 ms 6780 KB Output is correct
7 Correct 5 ms 6780 KB Output is correct
8 Correct 171 ms 6780 KB Output is correct
9 Correct 254 ms 11080 KB Output is correct
10 Correct 248 ms 11080 KB Output is correct
11 Correct 167 ms 11080 KB Output is correct
12 Correct 203 ms 11080 KB Output is correct
13 Correct 205 ms 11080 KB Output is correct
14 Correct 296 ms 11080 KB Output is correct
15 Correct 290 ms 11080 KB Output is correct
16 Correct 261 ms 11080 KB Output is correct
17 Correct 264 ms 11080 KB Output is correct
18 Correct 267 ms 11080 KB Output is correct