oj.uz

Submission #758387

# Submission time Handle Problem Language Result Execution time Memory
758387 2023-06-14T14:30:19 Z vjudge1 Simple game (IZhO17_game) C++17
100 / 100
 295 ms 33140 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[5000000],lazy[5000000];
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
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 13 ms 24200 KB Output is correct
3 Correct 13 ms 23704 KB Output is correct
4 Correct 13 ms 24404 KB Output is correct
5 Correct 13 ms 24276 KB Output is correct
6 Correct 13 ms 24436 KB Output is correct
7 Correct 9 ms 18772 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 13 ms 24200 KB Output is correct
3 Correct 13 ms 23704 KB Output is correct
4 Correct 13 ms 24404 KB Output is correct
5 Correct 13 ms 24276 KB Output is correct
6 Correct 13 ms 24436 KB Output is correct
7 Correct 9 ms 18772 KB Output is correct
8 Correct 60 ms 1352 KB Output is correct
9 Correct 151 ms 33140 KB Output is correct
10 Correct 162 ms 32996 KB Output is correct
11 Correct 58 ms 1360 KB Output is correct
12 Correct 119 ms 2696 KB Output is correct
13 Correct 96 ms 33068 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 13 ms 24200 KB Output is correct
3 Correct 13 ms 23704 KB Output is correct
4 Correct 13 ms 24404 KB Output is correct
5 Correct 13 ms 24276 KB Output is correct
6 Correct 13 ms 24436 KB Output is correct
7 Correct 9 ms 18772 KB Output is correct
8 Correct 60 ms 1352 KB Output is correct
9 Correct 151 ms 33140 KB Output is correct
10 Correct 162 ms 32996 KB Output is correct
11 Correct 58 ms 1360 KB Output is correct
12 Correct 119 ms 2696 KB Output is correct
13 Correct 96 ms 33068 KB Output is correct
14 Correct 287 ms 32724 KB Output is correct
15 Correct 269 ms 32716 KB Output is correct
16 Correct 295 ms 32724 KB Output is correct
17 Correct 285 ms 32844 KB Output is correct
18 Correct 286 ms 32724 KB Output is correct