oj.uz

Submission #593310

# Submission time Handle Problem Language Result Execution time Memory
593310 2022-07-10T20:34:28 Z Lawliet Simple game (IZhO17_game) C++17
22 / 100
 6 ms 8404 KB 
#include <bits/stdc++.h>
 
#define MAX 1000010
 
using namespace std;
 
class FenwickTree
{
    public:
        
        void update(int i, int v)
        {
            for( ; i > 0 ; i -= i&-i)
                BIT[ i ] += v;
        }
 
        void sumInterval(int l, int r, int v)
        {
            update(r , v);
            if(l > 0) update(l - 1 , -v);
        }
        
        int query(int i)
        {
            int ans = 0;
 
            for( ; i < MAX ; i += i & -i)
                ans += BIT[ i ];
 
            return ans;
        }
 
        FenwickTree() { memset(BIT , 0 , sizeof(BIT)); }
        
    private:
        
        int BIT[MAX];
};
 
int n, m;
int n1, n2, n3;
 
int v[MAX];
 
FenwickTree BIT;
 
void update(int i, int k)
{
    if(2 <= i && i <= n) 
        BIT.sumInterval(min(v[ i ] , v[i - 1]) , max(v[i] , v[i - 1]) , k);
}
 
int main()
{
    scanf("%d %d",&n,&m);
 
    assert(n <= 1000);
    assert(m <= 1000);

    for(int g = 1 ; g <= n ; g++)
        scanf("%d",&v[g]);
 
    for(int g = 1 ; g <= n ; g++)
        update(g , 1);
 
    for(int g = 0 ; g < m ; g++)
    {
        scanf("%d %d",&n1,&n2);
 
        if(n1 == 1)
        {
            scanf("%d",&n3);
 
            update(n2 , -1);
            update(n2 + 1 , -1);
 
            v[ n2 ] = n3;
 
            update(n2 , 1);
            update(n2 + 1 , 1);
        }
        else printf("%d\n",BIT.query( n2 ));
    }
}

Compilation message

game.cpp: In function 'int main()':
game.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
game.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         scanf("%d",&v[g]);
      |         ~~~~~^~~~~~~~~~~~
game.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         scanf("%d %d",&n1,&n2);
      |         ~~~~~^~~~~~~~~~~~~~~~~
game.cpp:72:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |             scanf("%d",&n3);
      |             ~~~~~^~~~~~~~~~

Subtask #1
22.0 / 22.0

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

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 3 ms 4180 KB Output is correct
3 Correct 3 ms 4232 KB Output is correct
4 Correct 3 ms 4180 KB Output is correct
5 Correct 3 ms 4180 KB Output is correct
6 Correct 3 ms 4180 KB Output is correct
7 Correct 3 ms 4180 KB Output is correct
8 Runtime error 6 ms 8404 KB Execution killed with signal 6
9 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 3 ms 4180 KB Output is correct
3 Correct 3 ms 4232 KB Output is correct
4 Correct 3 ms 4180 KB Output is correct
5 Correct 3 ms 4180 KB Output is correct
6 Correct 3 ms 4180 KB Output is correct
7 Correct 3 ms 4180 KB Output is correct
8 Runtime error 6 ms 8404 KB Execution killed with signal 6
9 Halted 0 ms 0 KB -