oj.uz

Submission #290335

# Submission time Handle Problem Language Result Execution time Memory
290335 2020-09-03T16:05:57 Z MasterTaster Simple game (IZhO17_game) C++14
100 / 100
 499 ms 17784 KB 
#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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 512 KB Output is correct
2 Correct 13 ms 14976 KB Output is correct
3 Correct 13 ms 14720 KB Output is correct
4 Correct 13 ms 14976 KB Output is correct
5 Correct 16 ms 15104 KB Output is correct
6 Correct 13 ms 14976 KB Output is correct
7 Correct 17 ms 12800 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 512 KB Output is correct
2 Correct 13 ms 14976 KB Output is correct
3 Correct 13 ms 14720 KB Output is correct
4 Correct 13 ms 14976 KB Output is correct
5 Correct 16 ms 15104 KB Output is correct
6 Correct 13 ms 14976 KB Output is correct
7 Correct 17 ms 12800 KB Output is correct
8 Correct 98 ms 1092 KB Output is correct
9 Correct 268 ms 17776 KB Output is correct
10 Correct 243 ms 17784 KB Output is correct
11 Correct 96 ms 1016 KB Output is correct
12 Correct 142 ms 2040 KB Output is correct
13 Correct 204 ms 17784 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 512 KB Output is correct
2 Correct 13 ms 14976 KB Output is correct
3 Correct 13 ms 14720 KB Output is correct
4 Correct 13 ms 14976 KB Output is correct
5 Correct 16 ms 15104 KB Output is correct
6 Correct 13 ms 14976 KB Output is correct
7 Correct 17 ms 12800 KB Output is correct
8 Correct 98 ms 1092 KB Output is correct
9 Correct 268 ms 17776 KB Output is correct
10 Correct 243 ms 17784 KB Output is correct
11 Correct 96 ms 1016 KB Output is correct
12 Correct 142 ms 2040 KB Output is correct
13 Correct 204 ms 17784 KB Output is correct
14 Correct 499 ms 17444 KB Output is correct
15 Correct 470 ms 17588 KB Output is correct
16 Correct 477 ms 17528 KB Output is correct
17 Correct 486 ms 17424 KB Output is correct
18 Correct 463 ms 17528 KB Output is correct