Submission #1174776

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174776		rafsanamin2020	Simple game (IZhO17_game)	C++20	100 / 100	167 ms	20624 KiB

game

#include <bits/stdc++.h>
using namespace std;

const int MAX = 1E6 + 11;

vector<int> tree(4 * MAX + 1, 0);
vector<int> val(MAX + 1, 0);

void update(int l, int r, bool del, int at = 1, int lo = 1, int hi = MAX)
{
  int lc = at * 2, rc = at * 2 + 1, mid = (lo + hi) / 2;

  if (l > hi || r < lo)
  {
    return;
  }

  if (l == lo && r == hi)
  {
    if (!del)
    {
      tree[at]++;
      // cout << l << " " << r << " " << lo << " " << hi << "\n";
    }
    else
    {
      tree[at]--;
    }
    return;
  }

  update(l, min(r, mid), del, lc, lo, mid);
  update(max(l, mid + 1), r, del, rc, mid + 1, hi);
}

int query(int v, int at = 1, int lo = 1, int hi = MAX)
{
  int lc = at * 2, rc = at * 2 + 1, mid = (lo + hi) / 2;
  if (v > hi || v < lo)
  {
    return 0;
  }
  if (lo == hi && hi == v)
  {
    return tree[at];
  }

  return tree[at] + query(v, lc, lo, mid) + query(v, rc, mid + 1, hi);
}

void q(int l, int r, bool del)
{
  int temp = min(l, r);
  r = max(l, r);
  l = temp;
  update(l, r, del);
}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int N, M;
  cin >> N >> M;

  for (int i = 0; i < N; i++)
  {
    cin >> val[i + 1];
  }

  for (int i = 1; i < N; i++)
  {
    // cout << val[i] << " " << val[i + 1] << "\t";
    q(val[i], val[i + 1], false);
  }

  for (int i = 0; i < M; i++)
  {
    int t;
    cin >> t;
    if (t == 1)
    {
      int j, v;
      cin >> j >> v;

      // delete ager value
      if (j != N)
      {
        q(val[j], val[j + 1], true);
        q(v, val[j + 1], false);
      }

      if (j != 1)
      {
        q(val[j - 1], val[j], true);
        q(val[j - 1], v, false);
      }
      // add  new value

      val[j] = v;
    }
    else
    {
      int k;
      cin >> k;
      cout << query(k) << "\n";
    }
  }
}

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