Submission #85311

#	Time	Username	Problem	Language	Result	Execution time	Memory
85311		muradeyn	Simple game (IZhO17_game)	C++14	100 / 100	518 ms	25592 KiB

game

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