제출 #1293697

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1293697		Gadir_2880	Simple game (IZhO17_game)	C++20	0 / 100	5 ms	8252 KiB

game

//The Rumbling starts here:
 
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
 
#include<bits/stdc++.h>
using namespace std;
#define debug(n,m) cout<<"["<<#n<<"]->"<<n<<m
#define int long long
#define all(x) x.begin(),x.end() 
#define ai array<int,2>
#define vv vector
#define pb push_back
 
const int N=1e6+5;
const int mod=1e9+7;
const int inf=(1ll<<55)-1;

int a[N];
int n,q;

struct Fenwick {

  vector<int> tr;
  
  void init(int n) {
    tr.assign(n+5,0);
  }
  
  void upd(int k, int x) {
    for (;k<=n;k+=k&-k) {
      tr[k]+=x;
    }
  }
  
  int sum(int k) {
    int res=0;
    for (;k>0;k-=k&-k) {
      res+=tr[k];
    }
    return res;
  }
  
  int query(int l,int r) {
    if (l>r) return 0;
    return sum(r)-sum(l-1);
  }
};

void levi() {
  cin>>n>>q;
  for (int i=1;i<=n;i++) {
    cin>>a[i];
  }
  Fenwick s;
  s.init(N);
  for (int i=1;i<n;i++) {
    int l=a[i];
    int r=a[i+1];
    if (l>r) swap(l,r);
    s.upd(l,1);
    s.upd(r+1,-1);
  }
  for (int i=1;i<=q;i++) {
    int t;
    cin>>t;
    if (t==1) {
      int k,x;
      cin>>k>>x;
      if (k>1) {
        int l=a[k-1];
        int r=a[k];
        if (l>r) swap(l,r);
        s.upd(l,-1);
        s.upd(r+1,1);
        l=a[k-1];
        r=x;
        if (l>r) swap(l,r);
        s.upd(l,1);
        s.upd(r+1,-1);
      }
      if (k<n) {
        int l=a[k];
        int r=a[k+1];
        if (l>r) swap(l,r);
        s.upd(l,-1);
        s.upd(r+1,1);
        l=a[k+1];
        r=x;
        if (l>r) swap(l,r);
        s.upd(l,1);
        s.upd(r+1,-1);
      }
      a[k]=x;
    }
    else {
      int h;
      cin>>h;
      cout<<s.sum(h)<<'\n';
    }
  }
}

int32_t main() {
  // freopen("bbreeds.in","r",stdin);
  // freopen("bbreeds.out","w",stdout);
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int tt=1;
  #ifdef tests
  cin>>tt;
  #endif
  while(tt--) levi();
}

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