Submission #758376

#	Time	Username	Problem	Language	Result	Execution time	Memory
758376		vjudge1	Simple game (IZhO17_game)	C++17	0 / 100	2 ms	1108 KiB

game

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define endl "\n"
int mod=1e7+9;
//const int N=1000005;//2e5+5;
template<class x>
using ordered_multiset = tree<x, null_type,less_equal<x>, rb_tree_tag,tree_order_statistics_node_update>;

int seg[1500000],lazy[1500000];
int N,Left,Right,i,c=-1;

void spread(int indx,int l,int r) {
  if (l!=r) {
    lazy[indx*2]+=lazy[indx];
    lazy[indx*2+1]+=lazy[indx];
    seg[indx*2]+=lazy[indx];
    seg[indx*2+1]+=lazy[indx];
  }
  lazy[indx]=0;
 }

int query(int indx=1,int l=1,int r=N) {
  if (r<Left || l>Right) return 1e18;
  spread(indx,l,r);
  if (Left<=l && Right>=r) return seg[indx];

  int mid=(l+r)/2;
  return min(query(indx*2,l,mid),query(indx*2+1,mid+1,r));
}

void update(int indx=1,int l=1,int r=N) {
  if (r<Left || l>Right) return;
  spread(indx,l,r);
  if (Left<=l && Right>=r) {
    lazy[indx]+=c;
    seg[indx]+=c;
    return;
  }

  int mid=(l+r)/2;
  update(indx*2,l,mid);
  update(indx*2+1,mid+1,r);
  seg[indx]=seg[indx*2]+seg[indx*2+1];
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int n,m; cin>>n>>m;
    N=exp2(ceil(log2(1000005)));
    int v[n];
    for (int i=0;i<n;i++) cin>>v[i];
    for (int i=1;i<n;i++) {
      Left=min(v[i],v[i-1]);
      Right=max(v[i],v[i-1]);
      c=1;
      update();
    }

    while (m--) {
      int t; cin>>t;
      if (t==2) {
      int i; cin>>i;
      Left=Right=i;
      cout<<query()<<endl;
    }
    else {
      int i,val; cin>>i>>val;
      i--;
      if (i>=1) {
        Left=min(v[i],v[i-1]);
        Right=max(v[i],v[i-1]);
        c=-1;
        update();
        Left=min(val,v[i-1]);
        Right=max(val,v[i-1]);
        c=1;
        update();
      }
      if (i+1<n) {
        Left=min(v[i],v[i+1]);
        Right=max(v[i],v[i+1]);
        c=-1;
        update();
        Left=min(val,v[i+1]);
        Right=max(val,v[i+1]);
        c=1;
        update();
      }
      v[i]=val;
    }
  }

}

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