oj.uz

Submission #367590

# Submission time Handle Problem Language Result Execution time Memory
367590 2021-02-17T17:35:08 Z mohamedsobhi777 Simple game (IZhO17_game) C++14
100 / 100
 94 ms 10988 KB 
#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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8172 KB Output is correct
2 Correct 6 ms 8172 KB Output is correct
3 Correct 6 ms 8172 KB Output is correct
4 Correct 6 ms 8172 KB Output is correct
5 Correct 6 ms 8172 KB Output is correct
6 Correct 6 ms 8172 KB Output is correct
7 Correct 5 ms 8172 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8172 KB Output is correct
2 Correct 6 ms 8172 KB Output is correct
3 Correct 6 ms 8172 KB Output is correct
4 Correct 6 ms 8172 KB Output is correct
5 Correct 6 ms 8172 KB Output is correct
6 Correct 6 ms 8172 KB Output is correct
7 Correct 5 ms 8172 KB Output is correct
8 Correct 42 ms 9068 KB Output is correct
9 Correct 71 ms 10872 KB Output is correct
10 Correct 72 ms 10860 KB Output is correct
11 Correct 41 ms 9452 KB Output is correct
12 Correct 49 ms 10604 KB Output is correct
13 Correct 59 ms 10604 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8172 KB Output is correct
2 Correct 6 ms 8172 KB Output is correct
3 Correct 6 ms 8172 KB Output is correct
4 Correct 6 ms 8172 KB Output is correct
5 Correct 6 ms 8172 KB Output is correct
6 Correct 6 ms 8172 KB Output is correct
7 Correct 5 ms 8172 KB Output is correct
8 Correct 42 ms 9068 KB Output is correct
9 Correct 71 ms 10872 KB Output is correct
10 Correct 72 ms 10860 KB Output is correct
11 Correct 41 ms 9452 KB Output is correct
12 Correct 49 ms 10604 KB Output is correct
13 Correct 59 ms 10604 KB Output is correct
14 Correct 93 ms 10988 KB Output is correct
15 Correct 87 ms 10732 KB Output is correct
16 Correct 91 ms 10748 KB Output is correct
17 Correct 88 ms 10732 KB Output is correct
18 Correct 94 ms 10860 KB Output is correct