oj.uz

Submission #85311

# Submission time Handle Problem Language Result Execution time Memory
85311 2018-11-19T08:46:47 Z muradeyn Simple game (IZhO17_game) C++14
100 / 100
 518 ms 25592 KB 
/* Murad Eynizade */

#include <bits/stdc++.h>
#define intt long long
#define FAST_READ ios_base::sync_with_stdio(0);cin.tie(0);
#define SIZE 1000001
#define INF INT_MAX
#define F first
#define S second
#define in(a) scanf("%d",&a);
#define outn(a) printf("%d\n",&a);
#define outs(a) printf("%d ",&a);
#define MOD 1000000007

using namespace std;

int n , m , tree[4 * SIZE] , lazy[4 * SIZE];

void update(int v,int l,int r,int le,int ri,int val) {
    if (ri < le)return;
    if (lazy[v] != 0) {
        tree[v] += lazy[v] * (r - l + 1);
        lazy[v << 1] += lazy[v];
        lazy[v << 1 | 1] += lazy[v];
        lazy[v] = 0;
    }
    if (l > ri || r < le)return;
    if (l >= le && r <= ri) {
        tree[v] += val * (r - l + 1);
        lazy[v << 1]+=val;
        lazy[v << 1 | 1]+=val;
        return;
    }
    int m = (l + r) >> 1;
    update(v << 1,l,m,le,ri,val);
    update(v << 1 | 1,m + 1,r,le,ri,val);
    tree[v] = tree[v << 1] + tree[v << 1 | 1];
}

int getans(int v,int l,int r,int le,int ri) {
    //cout<<l<<" "<<r<<" "<<le<<" "<<ri<<endl;
    //char aa;
    //cin>>aa;
    //cout<<l<<" "<<r<<" "<<v<<" "<<lazy[v]<<endl;
    if (lazy[v] != 0) {
        tree[v] += lazy[v] * (r - l + 1);
        lazy[v << 1] += lazy[v];
        lazy[v << 1 | 1] += lazy[v];
        lazy[v] = 0;
    }
    if (l > ri || r < le) return 0;
    if (l >= le && r <= ri)return tree[v];
    int m = (l + r) >> 1;
    return getans(v << 1,l,m,le,ri) + getans(v << 1 | 1,m + 1,r,le,ri);
}

int ty , x , y;

int main()
{
    FAST_READ;
    cin>>n>>m;
    int h[n];
    for (int i = 0;i<n;i++) {
        cin>>h[i];
        if (i != 0)update(1,1,SIZE - 1,min(h[i],h[i - 1]) + 1,max(h[i],h[i - 1]) - 1,1);
    }
    while (m--) {
        cin>>ty;
        if (ty == 1) {
            cin>>x>>y;
            x--;
            if (x > 0)update(1,1,SIZE - 1,min(h[x],h[x - 1]) + 1,max(h[x],h[x - 1]) - 1,-1);
            if (x < n - 1)update(1,1,SIZE - 1,min(h[x],h[x + 1]) + 1,max(h[x],h[x + 1]) - 1,-1);
            h[x] = y;
            if (x > 0)update(1,1,SIZE - 1,min(h[x],h[x - 1]) + 1,max(h[x],h[x - 1]) - 1,1);
            if (x < n - 1)update(1,1,SIZE - 1,min(h[x],h[x + 1]) + 1,max(h[x],h[x + 1]) - 1,1);
        }
        else {
            cin>>x;
            cout<<getans(1,1,SIZE - 1,x,x)<<endl;
        }
    }
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 22 ms 19172 KB Output is correct
3 Correct 24 ms 19172 KB Output is correct
4 Correct 22 ms 19200 KB Output is correct
5 Correct 25 ms 19200 KB Output is correct
6 Correct 23 ms 19200 KB Output is correct
7 Correct 16 ms 19200 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 22 ms 19172 KB Output is correct
3 Correct 24 ms 19172 KB Output is correct
4 Correct 22 ms 19200 KB Output is correct
5 Correct 25 ms 19200 KB Output is correct
6 Correct 23 ms 19200 KB Output is correct
7 Correct 16 ms 19200 KB Output is correct
8 Correct 216 ms 19200 KB Output is correct
9 Correct 386 ms 25364 KB Output is correct
10 Correct 400 ms 25592 KB Output is correct
11 Correct 194 ms 25592 KB Output is correct
12 Correct 273 ms 25592 KB Output is correct
13 Correct 342 ms 25592 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 22 ms 19172 KB Output is correct
3 Correct 24 ms 19172 KB Output is correct
4 Correct 22 ms 19200 KB Output is correct
5 Correct 25 ms 19200 KB Output is correct
6 Correct 23 ms 19200 KB Output is correct
7 Correct 16 ms 19200 KB Output is correct
8 Correct 216 ms 19200 KB Output is correct
9 Correct 386 ms 25364 KB Output is correct
10 Correct 400 ms 25592 KB Output is correct
11 Correct 194 ms 25592 KB Output is correct
12 Correct 273 ms 25592 KB Output is correct
13 Correct 342 ms 25592 KB Output is correct
14 Correct 507 ms 25592 KB Output is correct
15 Correct 518 ms 25592 KB Output is correct
16 Correct 505 ms 25592 KB Output is correct
17 Correct 511 ms 25592 KB Output is correct
18 Correct 510 ms 25592 KB Output is correct