제출 #290335

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
290335		MasterTaster	Simple game (IZhO17_game)	C++14	100 / 100	499 ms	17784 KiB

game

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define pii pair<int, int>
#define xx first
#define yy second
#define endl "\n"
#define MAXN 1000007
#define MAXH 1000001

int n, m, arr[100010], bit[1000010], seg[4000010], lazy[4000010];

void upd(int x, int v)
{
    while(x<MAXN)
    {
        bit[x]+=v;
        x+=x&(-x);
    }
}
int sum(int x)
{
    int suma=0;
    while (x)
    {
        suma+=bit[x];
        x-=x&(-x);
    }
    return suma;
}

void relax(int node, int l, int r)
{
    seg[node]+=(r-l+1)*(lazy[node]);
    if (l!=r)
    {
        lazy[2*node]+=lazy[node];
        lazy[2*node+1]+=lazy[node];
    }
    lazy[node]=0;
}

void upd(int node, int l, int r, int levo, int desno, int val) ///[l, r]-gde sam u segmentnom; [levo, desno]-query
{
    relax(node, l, r);
    if (levo>r || desno<l) return;
    if (levo<=l && desno>=r)
    {
        lazy[node]+=val;
        return;
    }
    int mid=l+(r-l)/2;
    upd(2*node, l, mid, levo, desno, val);
    upd(2*node+1, mid+1, r, levo, desno, val);
    seg[node]=seg[2*node]+seg[2*node+1];
}
int query(int node, int l, int r, int levo, int desno)
{
    relax(node, l, r);
    if (levo>r || desno<l) return 0;
    if (levo<=l && desno>=r) return seg[node];

    int mid=l+(r-l)/2;
    return (query(2*node, l, mid, levo, desno)+
            query(2*node+1, mid+1, r, levo, desno));

}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin>>n>>m;

    for (int i=0; i<n; i++) cin>>arr[i];

    for (int i=1; i<n; i++)
    {
        int l=min(arr[i], arr[i-1]), r=max(arr[i], arr[i-1]);
        upd(1, 0, MAXH, l, r, 1);
    }

    while (m--)
    {
        int q; cin>>q;
        if (q==1)
        {
            int i, x; cin>>i>>x;
            i--;
            if (i!=0)
            {
                int l=min(arr[i], arr[i-1]), r=max(arr[i], arr[i-1]);
                upd(1, 0, MAXH, l, r, -1);
                l=min(x, arr[i-1]), r=max(x, arr[i-1]);
                upd(1, 0, MAXH, l, r, 1);
            }
            if (i!=n-1)
            {
                int l=min(arr[i], arr[i+1]), r=max(arr[i], arr[i+1]);
                upd(1, 0, MAXH, l, r, -1);
                l=min(x, arr[i+1]), r=max(x, arr[i+1]);
                upd(1, 0, MAXH, l, r, 1);
            }
            arr[i]=x;

            /*if (i!=0)
            {
                upd(min(arr[i], arr[i-1]), -1);
                upd(max(arr[i], arr[i-1])+1, 1);

                upd(min(x, arr[i-1]), 1);
                upd(max(x, arr[i-1])+1, -1);
            }
            if (i!=n-1)
            {
                upd(min(arr[i], arr[i+1]), -1);
                upd(max(arr[i], arr[i+1])+1, 1);

                upd(min(x, arr[i+1]), 1);
                upd(max(x, arr[i+1])+1, -1);
            }
            arr[i]=x;*/
        }
        else
        {
            int h; cin>>h;
            cout<<query(1, 0, MAXH, h, h)<<endl;
            //cout<<sum(h)<<endl;
        }
    }
}

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