Submission #172678

#	Time	Username	Problem	Language	Result	Execution time	Memory
172678		RafaelSus	Simple game (IZhO17_game)	C++14	100 / 100	355 ms	19684 KiB

game

#include <bits/stdc++.h>
 
using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
const ll inf=1e15;
#define pb push_back
const int INF=(0x3f3f3f3f);

int h[N];
int T[N*20];
int lazy[N*20];

inline void pushdown(int v,int tl,int tr){
  if(lazy[v]==0)return;
  int tm=(tl+tr)/2;
  lazy[v+v]+=lazy[v];
  lazy[v+v+1]+=lazy[v];
  T[v+v]+=(tm-tl+1)*lazy[v];
  T[v+v+1]+=(tr-tm)*lazy[v];
  lazy[v]=0;
}

void update(int v,int tl,int tr,int l,int r,int val){
  if(l>r)return;
  if(l<=tl&&r>=tr){
    T[v]+=(tr-tl+1)*val;
    lazy[v]+=val;
    return;
  }
  pushdown(v,tl,tr);
  int tm=(tl+tr)/2;
  if(l<=tm)update(v+v,tl,tm,l,r,val);
  if(r>=tm+1)update(v+v+1,tm+1,tr,l,r,val);
  T[v]=T[v+v]+T[v+v+1];
}

int get(int v,int tl,int tr,int pos){
  if(tl==tr){
    return T[v];
  }
  pushdown(v,tl,tr);
  int tm=(tl+tr)/2;
  if(pos<=tm)return get(v+v,tl,tm,pos);
  if(pos>tm)return get(v+v+1,tm+1,tr,pos);
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);cout.tie(0);

  int n,m;
  cin>>n>>m;
  for(int i=1;i<=n;i++){
    cin>>h[i];
    if(i>1){
      update(1,1,1000000,min(h[i],h[i-1]),max(h[i],h[i-1]),+1);
    }
  }
  for(int i=0;i<m;i++){
    int com;
    cin>>com;
    if(com==1){
      int pos,val;
      cin>>pos>>val;
      if(pos==1){
        update(1,1,1000000,min(h[pos],h[pos+1]),max(h[pos],h[pos+1]),-1);
        h[pos]=val;
        update(1,1,1000000,min(h[pos],h[pos+1]),max(h[pos],h[pos+1]),+1);
      }else if(pos==n){
        update(1,1,1000000,min(h[pos],h[pos-1]),max(h[pos],h[pos-1]),-1);
        h[pos]=val;
        update(1,1,1000000,min(h[pos],h[pos-1]),max(h[pos],h[pos-1]),+1);
      }else{
        update(1,1,1000000,min(h[pos],h[pos+1]),max(h[pos],h[pos+1]),-1);
        update(1,1,1000000,min(h[pos],h[pos-1]),max(h[pos],h[pos-1]),-1);
        h[pos]=val;
        update(1,1,1000000,min(h[pos],h[pos+1]),max(h[pos],h[pos+1]),+1);
        update(1,1,1000000,min(h[pos],h[pos-1]),max(h[pos],h[pos-1]),+1);
      }
    }else{
      int H;
      cin>>H;
      cout<<get(1,1,1000000,H)<<'\n';
    }
  }
}

Compilation message (stderr)

game.cpp: In function 'int get(int, int, int, int)':
game.cpp:46:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

• Subtask 1: 22 / 22
• Subtask 2: 27 / 27
• Subtask 3: 51 / 51