oj.uz

Submission #483510

# Submission time Handle Problem Language Result Execution time Memory
483510 2021-10-30T06:24:49 Z ak2006 Simple game (IZhO17_game) C++14
100 / 100
 211 ms 7064 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vb = vector<bool>;
using vvb = vector<vb>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<string>;
const ll mod = 1e9 + 7,inf = 1e18;
#define pb push_back
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
void setIO()
{
    fast;
}
vi bit(1e6 + 1);
void add(int i,int v)
{
    for (;i<=1e6;i += i & (-i))bit[i] += v;
}
void add(int l,int r,int v)
{
    add(l,v);
    add(r + 1,-v);
}
int get(int i)
{
    int ret = 0;
    for (;i>0;i -= i &(-i))ret += bit[i];
    return ret;
}
int main()
{
    setIO();
    int n,q;
    cin>>n>>q;
    vi h(n + 1);
    for (int i = 1;i<=n;i++){
        cin>>h[i];
        if (i >= 2)
            add(min(h[i - 1],h[i]),max(h[i - 1],h[i]),1);
    }
    while (q--){
        int t;
        cin>>t;
        if (t == 1){
            int p,v;
            cin>>p>>v;
            if (p >= 2)
                add(min(h[p - 1],h[p]),max(h[p - 1],h[p]),-1);
            if (p < n)
                add(min(h[p],h[p + 1]),max(h[p],h[p + 1]),-1);
            h[p] = v;
            if (p >= 2)
                add(min(h[p - 1],h[p]),max(h[p - 1],h[p]),1);
            if (p < n)
                add(min(h[p],h[p + 1]),max(h[p],h[p + 1]),1);
        }
        else{
            int H;
            cin>>H;
            cout<<get(H)<<endl;
        }
    }
    return 0;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4172 KB Output is correct
2 Correct 3 ms 4172 KB Output is correct
3 Correct 3 ms 4172 KB Output is correct
4 Correct 3 ms 4172 KB Output is correct
5 Correct 5 ms 4172 KB Output is correct
6 Correct 3 ms 4172 KB Output is correct
7 Correct 4 ms 4172 KB Output is correct
8 Correct 140 ms 5032 KB Output is correct
9 Correct 153 ms 7064 KB Output is correct
10 Correct 211 ms 6744 KB Output is correct
11 Correct 139 ms 5480 KB Output is correct
12 Correct 141 ms 6564 KB Output is correct
13 Correct 150 ms 6596 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4172 KB Output is correct
2 Correct 3 ms 4172 KB Output is correct
3 Correct 3 ms 4172 KB Output is correct
4 Correct 3 ms 4172 KB Output is correct
5 Correct 5 ms 4172 KB Output is correct
6 Correct 3 ms 4172 KB Output is correct
7 Correct 4 ms 4172 KB Output is correct
8 Correct 140 ms 5032 KB Output is correct
9 Correct 153 ms 7064 KB Output is correct
10 Correct 211 ms 6744 KB Output is correct
11 Correct 139 ms 5480 KB Output is correct
12 Correct 141 ms 6564 KB Output is correct
13 Correct 150 ms 6596 KB Output is correct
14 Correct 120 ms 6788 KB Output is correct
15 Correct 122 ms 6820 KB Output is correct
16 Correct 141 ms 6836 KB Output is correct
17 Correct 105 ms 6792 KB Output is correct
18 Correct 110 ms 6824 KB Output is correct