Submission #683974

#	Time	Username	Problem	Language	Result	Execution time	Memory
683974		speedyArda	Simple game (IZhO17_game)	C++14	100 / 100	414 ms	19344 KiB

game

#include "bits/stdc++.h"

using namespace std;
const int MAXN = 1e6;
int seg[MAXN * 4 + 5], lazy[MAXN * 4 + 5], height[MAXN + 5];

void push(int v)
{
    lazy[v * 2] += lazy[v];
    lazy[v * 2 + 1] += lazy[v];
    seg[v * 2] += lazy[v];
    seg[v * 2 + 1] += lazy[v];
    lazy[v] = 0;
}

void update(int v, int tl, int tr, int l, int r, int add)
{
    //cout << v << " " << l << " " << r<< "\n";
    if(l > r)
        return;
    if(l == tl && r == tr)
    {
        seg[v] += add;
        lazy[v] += add;
        return;
    }
    push(v);
    int tm = (tl + tr) / 2;

    update(2 * v, tl, tm, l, min(tm, r), add);
    update(2 * v + 1, tm + 1, tr, max(tm + 1, l), r, add);
}

int get(int v, int tl, int tr, int pos)
{
    if(tl == tr)
        return seg[v];
    push(v);
    int tm = (tl + tr) / 2;
    if(tm >= pos)
        return get(2 * v, tl, tm, pos);
    else
        return get(2 * v + 1, tm + 1, tr, pos);
}

int main() 
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> height[i];
        if(i > 1)
        {
            //cout << min(height[i], height[i - 1]) << " " << max(height[i], height[i - 1]) << "\n";
            update(1, 1, MAXN, min(height[i], height[i - 1]), max(height[i], height[i - 1]), 1);
        }
    }

    for(int i = 1; i <= m; i++)
    {
        int type;
        cin >> type;
        if(type == 1)
        {
            int idx, val;
            cin >> idx >> val;
            //cout << height[idx - 1] << " " << height[idx] << " " << height[idx + 1] << "\n";
            if(idx > 1)
                update(1, 1, MAXN, min(height[idx], height[idx - 1]), max(height[idx], height[idx - 1]), -1);
            if(idx < n)
                update(1, 1, MAXN, min(height[idx], height[idx + 1]), max(height[idx], height[idx + 1]), -1);
            height[idx] = val;
            if(idx > 1)
                update(1, 1, MAXN, min(height[idx], height[idx - 1]), max(height[idx], height[idx - 1]), 1);
            if(idx < n)
                update(1, 1, MAXN, min(height[idx], height[idx + 1]), max(height[idx], height[idx + 1]), 1);
        } else 
        {
            int h;
            cin >> h;
            cout << get(1, 1, MAXN, h) << "\n";
        }
    }
}

• Subtask 1: 22 / 22
• Subtask 2: 27 / 27
• Subtask 3: 51 / 51