oj.uz

Submission #571094

# Submission time Handle Problem Language Result Execution time Memory
571094 2022-06-01T08:40:41 Z YouAreMyGalaxy Simple game (IZhO17_game) C++17
100 / 100
 99 ms 6916 KB 
//Make CSP great again
//Vengeance
#include <bits/stdc++.h>
#define TASK "TESTCODE"
#define Log2(x) 31 - __builtin_clz(x)
using namespace std;
const int N = 1e5, M = 1e6;
struct FenwickTree
{
    int Tree[M + 1];
    void add(int pos, int val)
    {
        for (; pos <= M; pos += (pos & (-pos)))
        {
            Tree[pos] += val;
        }
    }
    int sum(int pos)
    {
        int ret = 0;
        for (; pos > 0; pos -= (pos & (-pos)))
        {
            ret += Tree[pos];
        }
        return ret;
    }
    int sum(int l, int r)
    {
        return sum(r) - sum(l - 1);
    }
} tree;
int h[N + 1], n, q;
void read()
{
    cin >> n >> q;
    for (int i = 1; i <= n; ++ i)
    {
        cin >> h[i];
        if (i > 1)
        {
            tree.add(min(h[i], h[i - 1]), 1);
            tree.add(max(h[i], h[i - 1]) + 1, -1);
        }
    }
}
void solve()
{
    while(q--)
    {
        int t;
        cin >> t;
        if (t == 1)
        {
            int i, a;
            cin >> i >> a;
            if (i < n)
            {
                tree.add(min(h[i], h[i + 1]), -1);
                tree.add(max(h[i], h[i + 1]) + 1, 1);
                tree.add(min(a, h[i + 1]), 1);
                tree.add(max(a, h[i + 1]) + 1, -1);
            }
            if (i > 1)
            {
                tree.add(min(h[i], h[i - 1]), -1);
                tree.add(max(h[i], h[i - 1]) + 1, 1);
                tree.add(min(a, h[i - 1]), 1);
                tree.add(max(a, h[i - 1]) + 1, -1);
            }
            h[i] = a;
        }
        else
        {
            int H;
            cin >> H;
            cout << tree.sum(H) << '\n';
        }
    }
}
int  main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        //freopen(TASK".OUT", "w", stdout);
    }
    int t = 1;
    bool typetest = false;
    if (typetest)
    {
        cin >> t;
    }
    for (int __ = 1; __ <= t; ++ __)
    {
        //cout << "Case " << __ << ": ";
        read();
        solve();
    }
}

Compilation message

game.cpp: In function 'int main()':
game.cpp:86:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 4132 KB Output is correct
3 Correct 3 ms 4052 KB Output is correct
4 Correct 3 ms 4052 KB Output is correct
5 Correct 3 ms 4052 KB Output is correct
6 Correct 3 ms 4044 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 32 ms 1736 KB Output is correct
9 Correct 53 ms 6732 KB Output is correct
10 Correct 72 ms 6916 KB Output is correct
11 Correct 34 ms 1544 KB Output is correct
12 Correct 35 ms 2760 KB Output is correct
13 Correct 37 ms 2756 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 4132 KB Output is correct
3 Correct 3 ms 4052 KB Output is correct
4 Correct 3 ms 4052 KB Output is correct
5 Correct 3 ms 4052 KB Output is correct
6 Correct 3 ms 4044 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 32 ms 1736 KB Output is correct
9 Correct 53 ms 6732 KB Output is correct
10 Correct 72 ms 6916 KB Output is correct
11 Correct 34 ms 1544 KB Output is correct
12 Correct 35 ms 2760 KB Output is correct
13 Correct 37 ms 2756 KB Output is correct
14 Correct 84 ms 6744 KB Output is correct
15 Correct 99 ms 6832 KB Output is correct
16 Correct 73 ms 6744 KB Output is correct
17 Correct 61 ms 6832 KB Output is correct
18 Correct 64 ms 6760 KB Output is correct