Submission #169094

#	Time	Username	Problem	Language	Result	Execution time	Memory
169094		itgl	Simple game (IZhO17_game)	C++14	0 / 100	22 ms	19008 KiB

game

#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: 0 / 22
• Subtask 2: 0 / 27
• Subtask 3: 0 / 51