oj.uz

Submission #519906

# Submission time Handle Problem Language Result Execution time Memory
519906 2022-01-27T14:33:29 Z Be_dos Simple game (IZhO17_game) C++17
100 / 100
 299 ms 18596 KB 
#include <iostream>
#include <cmath>
#include <cctype>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <deque>
#include <stack>
#include <unordered_set>
#include <sstream>
#include <cstring>
#include <iomanip>
#include <queue>
#include <unordered_map>
#include <random>
#include <cfloat>
#include <chrono>
#include <bitset>
#include <complex>
#include <immintrin.h>
#include <cassert>

int32_t* segtree;

void add(int32_t node, int32_t left, int32_t right, int32_t query_left, int32_t query_right, int32_t x) {
    if(left >= query_right || right <= query_left)
        return;
    if(left >= query_left && right <= query_right) {
        segtree[node] += x;
        return;
    }
    int32_t m = (left + right) / 2;
    add(node * 2 + 1, left, m, query_left, query_right, x);
    add(node * 2 + 2, m, right, query_left, query_right, x);
}

int32_t get(int32_t node, int32_t left, int32_t right, int32_t ind) {
    if(right - left == 1)
        return segtree[node];
    int32_t m = (left + right) / 2;
    if(ind >= m)
        return segtree[node] + get(node * 2 + 2, m, right, ind);
    return segtree[node] + get(node * 2 + 1, left, m, ind);
}

int main() {
    int32_t n, m;
    std::cin >> n >> m;

    int32_t* arr = new int32_t[n];
    for(int32_t i = 0; i < n; i++)
        std::cin >> arr[i];

    segtree = new int32_t[4 * 1'000'005];
    for(int32_t i = 0; i < 4 * 1'000'005; i++)
        segtree[i] = 0;
    for(int32_t i = 0; i < n - 1; i++)
        add(0, 0, 1'000'005, std::min(arr[i], arr[i + 1]), std::max(arr[i], arr[i + 1]) + 1, 1);

    for(int32_t q = 0; q < m; q++) {
        int32_t type;
        std::cin >> type;

        if(type == 1) {
            int32_t pos, val;
            std::cin >> pos >> val;
            pos--;

            if(pos > 0) {
                add(0, 0, 1'000'005, std::min(arr[pos - 1], arr[pos]), std::max(arr[pos - 1], arr[pos]) + 1, -1);
                add(0, 0, 1'000'005, std::min(arr[pos - 1], val), std::max(arr[pos - 1], val) + 1, 1);
            }
            if(pos < n - 1) {
                add(0, 0, 1'000'005, std::min(arr[pos + 1], arr[pos]), std::max(arr[pos + 1], arr[pos]) + 1, -1);
                add(0, 0, 1'000'005, std::min(arr[pos + 1], val), std::max(arr[pos + 1], val) + 1, 1);
            }
            arr[pos] = val;
        } else {
            int32_t h;
            std::cin >> h;

            std::cout << get(0, 0, 1'000'005, h) << "\n";
        }
    }
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15948 KB Output is correct
2 Correct 9 ms 15948 KB Output is correct
3 Correct 10 ms 15940 KB Output is correct
4 Correct 9 ms 15912 KB Output is correct
5 Correct 10 ms 15948 KB Output is correct
6 Correct 9 ms 15920 KB Output is correct
7 Correct 8 ms 15948 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15948 KB Output is correct
2 Correct 9 ms 15948 KB Output is correct
3 Correct 10 ms 15940 KB Output is correct
4 Correct 9 ms 15912 KB Output is correct
5 Correct 10 ms 15948 KB Output is correct
6 Correct 9 ms 15920 KB Output is correct
7 Correct 8 ms 15948 KB Output is correct
8 Correct 187 ms 17324 KB Output is correct
9 Correct 257 ms 18596 KB Output is correct
10 Correct 253 ms 18468 KB Output is correct
11 Correct 179 ms 17244 KB Output is correct
12 Correct 224 ms 18216 KB Output is correct
13 Correct 228 ms 18360 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15948 KB Output is correct
2 Correct 9 ms 15948 KB Output is correct
3 Correct 10 ms 15940 KB Output is correct
4 Correct 9 ms 15912 KB Output is correct
5 Correct 10 ms 15948 KB Output is correct
6 Correct 9 ms 15920 KB Output is correct
7 Correct 8 ms 15948 KB Output is correct
8 Correct 187 ms 17324 KB Output is correct
9 Correct 257 ms 18596 KB Output is correct
10 Correct 253 ms 18468 KB Output is correct
11 Correct 179 ms 17244 KB Output is correct
12 Correct 224 ms 18216 KB Output is correct
13 Correct 228 ms 18360 KB Output is correct
14 Correct 291 ms 18540 KB Output is correct
15 Correct 275 ms 18500 KB Output is correct
16 Correct 299 ms 18588 KB Output is correct
17 Correct 269 ms 18536 KB Output is correct
18 Correct 274 ms 18444 KB Output is correct