oj.uz

Submission #169095

# Submission time Handle Problem Language Result Execution time Memory
169095 2019-12-18T11:27:16 Z itgl Simple game (IZhO17_game) C++14
100 / 100
 648 ms 25400 KB 
#include<bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define mp make_pair

using namespace std;

int n,m;
int a[100005];
int tree[4000005];
int lazy[4000005];

void update(int id, int L, int R, int l, int r,int x){
  if(lazy[id]!=0){
    tree[id]+=lazy[id]*(R - L + 1);
    lazy[id*2]+=lazy[id];
    lazy[id*2+1]+=lazy[id];
    lazy[id]=0;
  }
  if(l>R||r<L|| l>r) return;
  if(l<=L&&R<=r){
    tree[id]+=(R-L+1)*x;
    //cout << id << ' ' << tree[id] << '\n';
    lazy[id*2]+=x;
    lazy[id*2+1]+=x;
    return;
  }
  update(id*2,L,(L+R)/2,l,r,x);
  update(id*2+1,(L+R)/2+1,R,l,r,x);
  //tree[id]=tree[id*2]+tree[id*2+1];
}

int query(int id, int L, int R, int h){
  if(lazy[id] != 0)
  {
      tree[id] += lazy[id] * (R - L + 1);
      lazy[id * 2] += lazy[id];
      lazy[id * 2 + 1] += lazy[id];
      lazy[id] = 0;
  }
  if(h>R||h<L) return 0;
  if(h==R&&L==h){
    return tree[id];
  }
  return query(id*2, L, (L + R) / 2, h)+ query(id*2+1,(L + R) / 2 + 1, R, h);
}

int main(){
  cin >> n >> m;
  for(int i=1;i<=n;i++){
    cin >> a[i];
    if(i>1){
      update(1,1,1000000,min(a[i],a[i-1])+1,max(a[i],a[i-1])-1,1);
    }
  }

  while(m--){
    int k;
    cin >> k;
    //cout << k;
    if(k==1){
      int pos, val;
      cin >> pos >> val;
      if(pos>1){
        update(1,1,1000000,min(a[pos-1],a[pos])+1,max(a[pos],a[pos-1])-1,-1);
        update(1,1,1000000,min(val,a[pos-1])+1,max(val,a[pos-1])-1,1);
      }
      if(pos<n){
        update(1,1,1000000,min(a[pos],a[pos+1])+1,max(a[pos],a[pos+1])-1,-1);
        update(1,1,1000000,min(val,a[pos+1])+1,max(val,a[pos+1])-1,1);
      }
      a[pos]=val;
    }
    else{
      int h;
      cin >> h;
      cout << query(1,1,1000000,h) << '\n';
    }
  }


  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 26 ms 18936 KB Output is correct
3 Correct 21 ms 18552 KB Output is correct
4 Correct 22 ms 18936 KB Output is correct
5 Correct 22 ms 18808 KB Output is correct
6 Correct 22 ms 18796 KB Output is correct
7 Correct 18 ms 15612 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 26 ms 18936 KB Output is correct
3 Correct 21 ms 18552 KB Output is correct
4 Correct 22 ms 18936 KB Output is correct
5 Correct 22 ms 18808 KB Output is correct
6 Correct 22 ms 18796 KB Output is correct
7 Correct 18 ms 15612 KB Output is correct
8 Correct 386 ms 1136 KB Output is correct
9 Correct 563 ms 25400 KB Output is correct
10 Correct 564 ms 25244 KB Output is correct
11 Correct 362 ms 1152 KB Output is correct
12 Correct 464 ms 2424 KB Output is correct
13 Correct 522 ms 25328 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 26 ms 18936 KB Output is correct
3 Correct 21 ms 18552 KB Output is correct
4 Correct 22 ms 18936 KB Output is correct
5 Correct 22 ms 18808 KB Output is correct
6 Correct 22 ms 18796 KB Output is correct
7 Correct 18 ms 15612 KB Output is correct
8 Correct 386 ms 1136 KB Output is correct
9 Correct 563 ms 25400 KB Output is correct
10 Correct 564 ms 25244 KB Output is correct
11 Correct 362 ms 1152 KB Output is correct
12 Correct 464 ms 2424 KB Output is correct
13 Correct 522 ms 25328 KB Output is correct
14 Correct 612 ms 24952 KB Output is correct
15 Correct 619 ms 25000 KB Output is correct
16 Correct 619 ms 24952 KB Output is correct
17 Correct 648 ms 24964 KB Output is correct
18 Correct 617 ms 24808 KB Output is correct