oj.uz

Submission #519785

# Submission time Handle Problem Language Result Execution time Memory
519785 2022-01-27T10:33:34 Z Dasha_Gnedko Simple game (IZhO17_game) C++17
100 / 100
 67 ms 6968 KB 
#include <bits/stdc++.h>
 
//#include <ext/pb_ds/detail/standard_policies.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
 
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
 
using namespace std;
 
//using namespace __gnu_pbds;
//template <typename T> using ordered_set = tree <T, null_type, less < T >, rb_tree_tag, tree_order_statistics_node_update>;
 
mt19937 gen(time(0));
 
#define ll long long
#define ld long double
#define pb push_back
#define F first
#define S second
#define TIME clock() * 1.0 / CLOCKS_PER_SEC
#define sz(a) int32_t(a.size())
#define endl '\n'
//#define int long long
 
const int N = 1e6 + 100;
const int M = 31;
const int mod = 1e9 + 7;
const ll inf = 1e18 + 7;
 
struct Fenwick
{
    int f[N];
 
    void upd(int i, int zn)
    {
        for(; i < N; i = (i | (i + 1)))
            f[i] += zn;
    }
 
    int get(int i)
    {
        int ans = 0;
        for(; i >= 0; i = (i & (i + 1)) - 1)
            ans += f[i];
        return ans;
    }
};
 
Fenwick f;
int a[N];
 
void upd(int x, int y, int zn)
{
    if (x > y) swap(x, y);
    f.upd(x, zn);
    f.upd(y, -zn);
}
 
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    //freopen("game.in", "r", stdin);
    //freopen("game.out", "w", stdout);
#endif // LOCAL
 
    int n, q;
    cin >> n >> q;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
        if (i) upd(a[i - 1], a[i], 1);
    }
    while (q--)
    {
        int type;
        cin >> type;
        if (type == 1)
        {
            int i, x;
            cin >> i >> x;
            i--;
            if (i) upd(a[i], a[i - 1], -1);
            if (i + 1 < n) upd(a[i], a[i + 1], -1);
            a[i] = x;
            if (i) upd(a[i], a[i - 1], 1);
            if (i + 1 < n) upd(a[i], a[i + 1], 1);
        }
        if (type == 2)
        {
            int x;
            cin >> x;
            cout << f.get(x) << endl;
        }
    }
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 2 ms 4176 KB Output is correct
3 Correct 2 ms 4048 KB Output is correct
4 Correct 2 ms 4048 KB Output is correct
5 Correct 3 ms 4096 KB Output is correct
6 Correct 2 ms 4048 KB Output is correct
7 Correct 1 ms 336 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 2 ms 4176 KB Output is correct
3 Correct 2 ms 4048 KB Output is correct
4 Correct 2 ms 4048 KB Output is correct
5 Correct 3 ms 4096 KB Output is correct
6 Correct 2 ms 4048 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 30 ms 1736 KB Output is correct
9 Correct 38 ms 6752 KB Output is correct
10 Correct 46 ms 6740 KB Output is correct
11 Correct 40 ms 1608 KB Output is correct
12 Correct 33 ms 2812 KB Output is correct
13 Correct 33 ms 2760 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 2 ms 4176 KB Output is correct
3 Correct 2 ms 4048 KB Output is correct
4 Correct 2 ms 4048 KB Output is correct
5 Correct 3 ms 4096 KB Output is correct
6 Correct 2 ms 4048 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 30 ms 1736 KB Output is correct
9 Correct 38 ms 6752 KB Output is correct
10 Correct 46 ms 6740 KB Output is correct
11 Correct 40 ms 1608 KB Output is correct
12 Correct 33 ms 2812 KB Output is correct
13 Correct 33 ms 2760 KB Output is correct
14 Correct 64 ms 6840 KB Output is correct
15 Correct 54 ms 6792 KB Output is correct
16 Correct 67 ms 6736 KB Output is correct
17 Correct 58 ms 6832 KB Output is correct
18 Correct 66 ms 6968 KB Output is correct