Submission #339302

#	Time	Username	Problem	Language	Result	Execution time	Memory
339302		boykut	Simple game (IZhO17_game)	C++14	100 / 100	607 ms	19564 KiB

game

#include <iostream>
//#include <fstream>
#include <cmath>
#include <iomanip>
#include <set>
#include <queue>
#include <vector>
#include <functional>

using namespace std;

//#define int long long
#define pb push_back
#define sc second
#define fr first

#define IOS ios::sync_with_stdio(0);cin.tie(0);
#define mt make_tuple
#define all(a) (a).begin(),(a).end()
const int MAXN = 0, inf = 2e9;

int sm[4000100], tadd[4000100];
int N = 1000100;

void push(int v, int vl, int vr) {
   if (tadd[v] != 0) {
      sm[v] += tadd[v] * (vr - vl + 1);
      if (vl != vr) {
         tadd[v+v+1] += tadd[v];
         tadd[v+v+2] += tadd[v];
      }
      tadd[v] = 0;
   }
};
int rsq(int v, int vl, int vr, int l, int r) {
   push(v, vl, vr);
   if (r < vl || vr < l)
      return 0;
   if (l <= vl && vr <= r) {
      return sm[v];
   }
   int vm = (vl + vr) / 2;
   int ff = rsq(v+v+1, vl, vm, l, r);
   int ss = rsq(v+v+2, vm+1, vr, l, r);
   return ff + ss;
};
void add(int v, int vl, int vr, int l, int r, int val) {
   push(v, vl, vr);
   if (r < vl || vr < l)
      return;
   if (l <= vl && vr <= r) {
      tadd[v] = val;
      push(v, vl, vr);
      return;
   }
   int vm = (vl + vr) / 2;
   add(v+v+1, vl, vm, l, r, val);
   add(v+v+2, vm+1, vr, l, r, val);
};

void inc(int l, int r, int val) {
   add(0, 0, N - 1, min(l, r), max(l, r), val);
}

void solve() {
   int n, q;
   cin >> n >> q;
   vector <int> h(n);
   
   for (int i = 0; i < n; i++) {
      cin >> h[i];
      if (i) {
         inc(h[i], h[i - 1], +1);
      }
   }
   
   for (int tmp = q, t; tmp--;) {
      cin >> t;
      if (t == 1) {
         int pos, val;
         cin >> pos >> val;
         pos--;
         if (pos - 1 >=0) inc(h[pos], h[pos - 1], -1);
         if (pos + 1 < n) inc(h[pos], h[pos + 1], -1);
         h[pos] = val;
         if (pos - 1 >=0) inc(h[pos], h[pos - 1], +1);
         if (pos + 1 < n) inc(h[pos], h[pos + 1], +1);
      } else {
         int H;
         cin >> H;
         cout << rsq(0, 0, N - 1, H, H) << '\n';
      }
   }
   return;
}

signed main() {
   //IOS;
   int q = 1;
   //cin >> q;
   while (q --) {
      solve();
   }
   return 0;
}

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