제출 #367590

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
367590		mohamedsobhi777	Simple game (IZhO17_game)	C++14	100 / 100	94 ms	10988 KiB

game

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#pragma GCC optimize("-Ofast")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")

using namespace std;
using namespace __gnu_pbds;

#define vi vector<int>
#define vll vector<ll>
#define vii vector<pair<int, int>>
#define vvi vector<vi>
#define vvii vector<vii>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define loop(_) for (int __ = 0; __ < (_); ++__)
#define forn(i, n) for (int i = 0; i < n; ++i)
#define pb push_back
#define f first
#define s second
#define sz(_) ((int)_.size())
#define all(_) _.begin(), _.end()
#define uni(_) unique(_)
#define lb lower_bound
#define ub upper_bound
#define si set<int>
#define ms multiset<int>
#define qi queue<int>
#define pq prioriry_queue<int>
#define mi map<int, int>
#define inc(i, l, r) for (int i = l; i <= r; i++)
#define dec(i, l, r) for (int i = l; i >= r; i--)

using lll = __int128;
using ll = long long;
using ld = long double;

const int N = 1e6 + 7;
const ll mod = 1e9 + 7;
const ll inf = 2e18;

auto ra = [] {char *p = new char ; delete p ; return ll(p) ; };
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count() * (ra() | 1));
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> os;

int n, k;

int T;

struct fenwick
{
       int bit[N];
       fenwick()
       {
              memset(bit, 0, sizeof bit);
       }
       void add(int x, int v)
       {
              for (; x < N; x += x & -x)
                     bit[x] += v;
       }
       int upto(int x)
       {
              int ret = 0;
              for (; x; x -= x & -x)
                     ret += bit[x];
              return ret;
       }
       inline int query(int l, int r) { return upto(r) - upto(l - 1); }
} bot, up;

void solve(int x, int y, int d)
{
       if (x > y)
              swap(x, y);
       bot.add(y, d);
       up.add(x, d);
}

int main()
{
       ios_base::sync_with_stdio(0);
       cin.tie(0);
#ifndef ONLINE_JUDGE
#endif

       cin >> n >> k;
       vi a(n);
       for (auto &u : a)
              cin >> u;
       for (int i = 1; i < n; ++i)
              solve(a[i - 1], a[i], 1);

       for (int i = 0; i < k; ++i)
       {
              int t;
              cin >> t;
              if (t == 1)
              {
                     int v, x;
                     cin >> v >> x;
                     --v;
                     if (v + 1 < n)
                            solve(a[v], a[v + 1], -1);
                     if (v)
                            solve(a[v - 1], a[v], -1);
                     a[v] = x;
                     if (v + 1 < n)
                            solve(a[v], a[v + 1], 1);
                     if (v)
                            solve(a[v - 1], a[v], 1);
              }
              else
              {
                     int h;
                     cin >> h;
                     int ret = n - 1 - bot.query(1, h - 1) - up.query(h + 1, N - 1);
                     cout << ret << "\n";
              }
       }

       return 0;
}

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