oj.uz

Submission #879249

# Submission time Handle Problem Language Result Execution time Memory
879249 2023-11-27T03:39:48 Z 12345678 Simple game (IZhO17_game) C++17
100 / 100
 156 ms 11412 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5, mx=1e6+5;
int n, m, h[nx], t, x, y;

struct segtree
{
    int lz[4*mx];
    void pushlz(int l, int r, int i)
    {
        if (l==r) return;
        lz[2*i]+=lz[i];
        lz[2*i+1]+=lz[i];
        lz[i]=0;
    }
    void update(int l, int r, int i, int ql, int qr, int vl)
    {
        pushlz(l, r, i);
        if (ql<=l&&r<=qr) return lz[i]+=vl, pushlz(l, r, i), void();
        if (qr<l||r<ql) return;
        int md=(l+r)/2;
        update(l, md, 2*i, ql, qr, vl);
        update(md+1, r, 2*i+1, ql, qr, vl);
    }
    int query(int l, int r, int i, int idx)
    {
        pushlz(l, r, i);
        if (l==r) return lz[i];
        int md=(l+r)/2;
        if (idx<=md) return query(l, md, 2*i, idx);
        return query(md+1, r, 2*i+1, idx);
    }
} s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=n; i++) cin>>h[i];
    for (int i=2; i<=n; i++) s.update(1, mx-1, 1, min(h[i], h[i-1]), max(h[i], h[i-1]), 1);
    while (m--)
    {
        cin>>t;
        if (t==1) 
        {
            cin>>x>>y;
            if (x!=1) s.update(1, mx-1, 1, min(h[x], h[x-1]), max(h[x], h[x-1]), -1);
            if (x!=n) s.update(1, mx-1, 1, min(h[x+1], h[x]), max(h[x+1], h[x]), -1);
            h[x]=y;
            if (x!=1) s.update(1, mx-1, 1, min(h[x], h[x-1]), max(h[x], h[x-1]), 1);
            if (x!=n) s.update(1, mx-1, 1, min(h[x+1], h[x]), max(h[x+1], h[x]), 1);
        }
        else cin>>x, cout<<s.query(1, mx-1, 1, x)<<'\n';
    }
}

Subtask #1
22.0 / 22.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 3 ms 8796 KB Output is correct
3 Correct 3 ms 8796 KB Output is correct
4 Correct 3 ms 8796 KB Output is correct
5 Correct 3 ms 8796 KB Output is correct
6 Correct 3 ms 8796 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 41 ms 5844 KB Output is correct
9 Correct 80 ms 11412 KB Output is correct
10 Correct 72 ms 11392 KB Output is correct
11 Correct 39 ms 5744 KB Output is correct
12 Correct 59 ms 6736 KB Output is correct
13 Correct 48 ms 11136 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 3 ms 8796 KB Output is correct
3 Correct 3 ms 8796 KB Output is correct
4 Correct 3 ms 8796 KB Output is correct
5 Correct 3 ms 8796 KB Output is correct
6 Correct 3 ms 8796 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 41 ms 5844 KB Output is correct
9 Correct 80 ms 11412 KB Output is correct
10 Correct 72 ms 11392 KB Output is correct
11 Correct 39 ms 5744 KB Output is correct
12 Correct 59 ms 6736 KB Output is correct
13 Correct 48 ms 11136 KB Output is correct
14 Correct 156 ms 11304 KB Output is correct
15 Correct 146 ms 11344 KB Output is correct
16 Correct 144 ms 11240 KB Output is correct
17 Correct 147 ms 11348 KB Output is correct
18 Correct 145 ms 11392 KB Output is correct