제출 #367584

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
367584		mohamedsobhi777	Simple game (IZhO17_game)	C++14	22 / 100	660 ms	262148 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
{
       os bit[N];

       void add(pii v)
       {
              if (v.f > v.s)
                     swap(v.f, v.s);
              for (int i = v.f; i < N; i += i & -i)
                     bit[i].insert({v.s, ++T});
       }

       int get(int l, int r)
       {
              int ret = 0;
              for (int i = r; i; i -= i & -i)
              {
                     ret += sz(bit[i]) - bit[i].order_of_key(make_pair(r + 1, -1));
              }
              return ret;
       }
} pos, neg;

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)
       {
              pos.add({a[i - 1], a[i]});
       }
       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)
                            neg.add({a[v], a[v + 1]});
                     if (v)
                            neg.add({a[v - 1], a[v]});
                     a[v] = x;
                     if (v + 1 < n)
                            pos.add({a[v], a[v + 1]});
                     if (v)
                            pos.add({a[v - 1], a[v]});
              }
              else
              {
                     int h;
                     cin >> h;
                     int ret = pos.get(1, h) - neg.get(1, h);
                     cout << ret << "\n";
              }
       }

       return 0;
}

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