oj.uz

Submission #169928

# Submission time Handle Problem Language Result Execution time Memory
169928 2019-12-23T09:41:55 Z stefdasca Simple game (IZhO17_game) C++14
100 / 100
 305 ms 17508 KB 
#include<bits/stdc++.h>
#define god dimasi5eks
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define mod 1000000007
#define dancila 3.14159265359
#define eps 1e-9

using namespace std;

typedef long long ll;

int n, q;
int v[100002];
int aint[4000002];
int lazy[4000002];
void lz(int nod, int st, int dr)
{
    if(st != dr)
    {
        lazy[nod << 1] += lazy[nod];
        lazy[nod << 1|1] += lazy[nod];
    }
    else
        aint[nod] += lazy[nod];
    lazy[nod] = 0;
}
void add(int nod, int st, int dr, int L, int R, int vv)
{
    lz(nod, st, dr);
    if(dr < L || st > R)
        return;
    if(L <= st && dr <= R)
    {
        lazy[nod] += vv;
        lz(nod, st, dr);
        return;
    }
    int mid = (st + dr) / 2;
    add(nod << 1, st, mid, L, R, vv);
    add(nod << 1|1, mid + 1, dr, L, R, vv);
}
int query(int nod, int st, int dr, int x)
{
    lz(nod, st, dr);
    if(st == dr)
        return aint[nod];
    int mid = (st + dr) / 2;
    if(x <= mid)
        query(nod << 1, st, mid, x);
    else
        query(nod << 1|1, mid+1, dr, x);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> q;
    for(int i = 1; i <= n; ++i)
        cin >> v[i];
    for(int i = 1; i < n; ++i)
        add(1, 1, 1000000, min(v[i], v[i+1]), max(v[i], v[i+1]), 1);
    for(int i = 1; i <= q; ++i)
    {
        int tip;
        cin >> tip;
        if(tip == 1)
        {
            int pos, val;
            cin >> pos >> val;
            if(pos != 1)
                add(1, 1, 1000000, min(v[pos - 1], v[pos]), max(v[pos - 1], v[pos]), -1);
            if(pos != n)
                add(1, 1, 1000000, min(v[pos + 1], v[pos]), max(v[pos + 1], v[pos]), -1);
            v[pos] = val;
            if(pos != 1)
                add(1, 1, 1000000, min(v[pos - 1], v[pos]), max(v[pos - 1], v[pos]), 1);
            if(pos != n)
                add(1, 1, 1000000, min(v[pos + 1], v[pos]), max(v[pos + 1], v[pos]), 1);
        }
        else
        {
            int pos;
            cin >> pos;
            cout << query(1, 1, 1000000, pos) << '\n';
        }
    }
    return 0;
}

Compilation message

game.cpp: In function 'int query(int, int, int, int)':
game.cpp:56:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 13 ms 11640 KB Output is correct
3 Correct 13 ms 11384 KB Output is correct
4 Correct 14 ms 11516 KB Output is correct
5 Correct 14 ms 11740 KB Output is correct
6 Correct 13 ms 11512 KB Output is correct
7 Correct 10 ms 9208 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 13 ms 11640 KB Output is correct
3 Correct 13 ms 11384 KB Output is correct
4 Correct 14 ms 11516 KB Output is correct
5 Correct 14 ms 11740 KB Output is correct
6 Correct 13 ms 11512 KB Output is correct
7 Correct 10 ms 9208 KB Output is correct
8 Correct 72 ms 1880 KB Output is correct
9 Correct 154 ms 17372 KB Output is correct
10 Correct 154 ms 17448 KB Output is correct
11 Correct 64 ms 1656 KB Output is correct
12 Correct 104 ms 3220 KB Output is correct
13 Correct 87 ms 17160 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 13 ms 11640 KB Output is correct
3 Correct 13 ms 11384 KB Output is correct
4 Correct 14 ms 11516 KB Output is correct
5 Correct 14 ms 11740 KB Output is correct
6 Correct 13 ms 11512 KB Output is correct
7 Correct 10 ms 9208 KB Output is correct
8 Correct 72 ms 1880 KB Output is correct
9 Correct 154 ms 17372 KB Output is correct
10 Correct 154 ms 17448 KB Output is correct
11 Correct 64 ms 1656 KB Output is correct
12 Correct 104 ms 3220 KB Output is correct
13 Correct 87 ms 17160 KB Output is correct
14 Correct 295 ms 17432 KB Output is correct
15 Correct 299 ms 17480 KB Output is correct
16 Correct 295 ms 17400 KB Output is correct
17 Correct 305 ms 17492 KB Output is correct
18 Correct 303 ms 17508 KB Output is correct