oj.uz

Submission #758376

# Submission time Handle Problem Language Result Execution time Memory
758376 2023-06-14T14:22:45 Z vjudge1 Simple game (IZhO17_game) C++17
0 / 100
 2 ms 1108 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Runtime error 2 ms 1108 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Runtime error 2 ms 1108 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Runtime error 2 ms 1108 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -