oj.uz

Submission #910083

# Submission time Handle Problem Language Result Execution time Memory
910083 2024-01-17T21:15:16 Z raphaelp Simple game (IZhO17_game) C++14
22 / 100
 179 ms 7184 KB 
#include <bits/stdc++.h>
using namespace std;
#define LSOne(S) ((S) & (-S))

class FenwickTree
{
private:
    vector<int> ft;

public:
    FenwickTree(int x)
    {
        ft.assign(x, 0);
    }
    void update(int a, int b, int val)
    {
        for (int x = b; x; x -= LSOne(x))
            ft[x] += val;
        for (int x = a; x; x -= LSOne(x))
            ft[x] -= val;
    }
    int PSQ(int x)
    {
        int tot = 0;
        for (; x < ft.size(); x += LSOne(x))
            tot += ft[x];
        return tot;
    }
};
int main()
{
    int N, M;
    cin >> N >> M;
    vector<int> Tab(N);
    FenwickTree FT(1000000);
    for (int i = 0; i < N; i++)
    {
        cin >> Tab[i];
        if (i != 0)
        {
            FT.update(min(Tab[i], Tab[i - 1]), max(Tab[i], Tab[i - 1]), 1);
        }
    }
    for (int i = 0; i < M; i++)
    {
        int a;
        cin >> a;
        if (a == 1)
        {
            int p, val;
            cin >> p >> val;
            p--;
            if (p != 0)
                FT.update(min(Tab[p], Tab[p - 1]), max(Tab[p], Tab[p - 1]), -1);
            if (p != N - 1)
                FT.update(min(Tab[p], Tab[p + 1]), max(Tab[p], Tab[p + 1]), -1);
            Tab[p] = val;
            if (p != 0)
                FT.update(min(Tab[p], Tab[p - 1]), max(Tab[p], Tab[p - 1]), 1);
            if (p != N - 1)
                FT.update(min(Tab[p], Tab[p + 1]), max(Tab[p], Tab[p + 1]), 1);
        }
        else
        {
            int x;
            cin >> x;
            cout << FT.PSQ(x) << '\n';
        }
    }
}

Compilation message

game.cpp: In member function 'int FenwickTree::PSQ(int)':
game.cpp:25:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         for (; x < ft.size(); x += LSOne(x))
      |                ~~^~~~~~~~~~~

Subtask #1
22.0 / 22.0

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

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4188 KB Output is correct
2 Correct 3 ms 4188 KB Output is correct
3 Correct 3 ms 4188 KB Output is correct
4 Correct 3 ms 4288 KB Output is correct
5 Correct 3 ms 4188 KB Output is correct
6 Correct 3 ms 4188 KB Output is correct
7 Correct 3 ms 4288 KB Output is correct
8 Correct 158 ms 5712 KB Output is correct
9 Correct 178 ms 6740 KB Output is correct
10 Correct 179 ms 7184 KB Output is correct
11 Correct 170 ms 5784 KB Output is correct
12 Correct 171 ms 6532 KB Output is correct
13 Incorrect 174 ms 6736 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4188 KB Output is correct
2 Correct 3 ms 4188 KB Output is correct
3 Correct 3 ms 4188 KB Output is correct
4 Correct 3 ms 4288 KB Output is correct
5 Correct 3 ms 4188 KB Output is correct
6 Correct 3 ms 4188 KB Output is correct
7 Correct 3 ms 4288 KB Output is correct
8 Correct 158 ms 5712 KB Output is correct
9 Correct 178 ms 6740 KB Output is correct
10 Correct 179 ms 7184 KB Output is correct
11 Correct 170 ms 5784 KB Output is correct
12 Correct 171 ms 6532 KB Output is correct
13 Incorrect 174 ms 6736 KB Output isn't correct
14 Halted 0 ms 0 KB -