Submission #910083

#	Time	Username	Problem	Language	Result	Execution time	Memory
910083		raphaelp	Simple game (IZhO17_game)	C++14	22 / 100	179 ms	7184 KiB

game

#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 (stderr)

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 / 22
• Subtask 2: 0 / 27
• Subtask 3: 0 / 51