oj.uz

Submission #169055

# Submission time Handle Problem Language Result Execution time Memory
169055 2019-12-18T06:56:37 Z itgl Simple game (IZhO17_game) C++14
0 / 100
 20 ms 18424 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(l>R||r<L|| l>r) return;
  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<=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;
  int i,j;
  for(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;
      int t= val-a[pos];
      if(pos>1&&pos<n){
        if(a[pos]>a[pos-1]){
          if(a[pos]<a[pos+1]){
            if(t>0){
              update(1,1,1000000,a[pos]+1,val,-1);
            }else{
              update(1,1,1000000,val+1,a[pos],1);
            }
          }else{
            update(1,1,1000000,a[pos]+1,a[pos+1]-1,-1);
            update(1,1,1000000,a[pos+1]+1,val-1,1);
          }
        }else{
          if(t>0){
            update(1,1,1000000,a[pos],val-1,1);
          }else{
            if(val>a[pos+1]){
              update(1,1,1000000,val,a[pos]-1,-1);
            }else{
              update(1,1,1000000,a[pos+1]+1,a[pos]-1,-1);
              update(1,1,1000000,val+1,a[pos+1]-1,1);
            }
          }
        }
      }
      if(pos==1){
        if(a[pos]>a[pos+1]){
          if(t>0){
            update(1,1,1000000,a[pos],val-1,1);
          }
          else{
            update(1,1,1000000,val,a[pos]-1,-1);
          }
        }else{
          if(t>0){
            update(1,1,1000000,a[pos]+1,val,-1);
          }else{
            update(1,1,1000000,val+1,a[pos],1);
          }
        }
      }
      if(pos==n){
        if(a[pos]>a[pos-1]){
          if(t>0){
            update(1,1,1000000,a[pos],val-1,1);
          }
          else{
            if(val>a[pos-1]){
              update(1,1,1000000,val,a[pos]-1,-1);
            }else{
              update(1,1,1000000,a[pos-1]+1,a[pos]-1,-1);
              update(1,1,1000000,val+1,a[pos-1]-1,1);
            }
          }
        }else{
          if(t>0){
            if(val<a[pos-1]){
              update(1,1,1000000,a[pos]+1,val,-1);
            }else{
              update(1,1,1000000,a[pos]+1,a[pos-1]-1,-1);
              update(1,1,1000000,a[pos-1]+1,val-1,1);
            }
          }else{
            update(1,1,1000000,val+1,a[pos],1);
          }
        }
      }
    }
    else{
      int h;
      cin >> h;
      cout << query(1,1,1000000,h) << '\n';
    }
  }


  return 0;
}

Compilation message

game.cpp: In function 'int main()':
game.cpp:51:9: warning: unused variable 'j' [-Wunused-variable]
   int i,j;
         ^

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 20 ms 18424 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 20 ms 18424 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 20 ms 18424 KB Output isn't correct
3 Halted 0 ms 0 KB -