oj.uz

Submission #689936

# Submission time Handle Problem Language Result Execution time Memory
689936 2023-01-29T19:21:44 Z YENGOYAN Simple game (IZhO17_game) C++17
100 / 100
 186 ms 11196 KB 
/*
        //\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\\
        \\                                    //
        //  271828___182845__904523__53602__  \\
        \\  87___47____13______52____66__24_  //
        //  97___75____72______47____09___36  \\
        \\  999595_____74______96____69___67  //
        //  62___77____24______07____66__30_  \\
        \\  35___35____47______59____45713__  //
        //                                    \\
        \\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\//
                                                    */

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <climits>
#include <algorithm>
#include <random>
#include <queue>
#include <deque>
#include <iomanip>
#include <string>
#include <tuple>
#include <bitset>
#include <chrono>
#include <ctime>
#include <fstream>
#include <stack>
#include <cstdio>

using namespace std;
using ll = long long;
const int N = 3e5 + 5;
const ll mod = 1e9 + 7, inf = 1e18;

vector<int> seg;
int s = (1 << 20);

void modify(int l, int r, int lx, int rx, int u, int val) {
    if (lx >= l && rx <= r) {
        seg[u] += val;
        return;
    }
    if (lx > r || rx < l) return;
    int m = (lx + rx) / 2;
    modify(l, r, lx, m, 2 * u + 1, val), modify(l, r, m + 1, rx, 2 * u + 2, val);
}

int get(int l, int r, int u, int i) {
    if (l == r)return seg[u];
    int m = (l + r) / 2;
    if (i <= m) return seg[u] + get(l, m, 2 * u + 1, i);
    else return seg[u] + get(m + 1, r, 2 * u + 2, i);
}

void solve() {
    // start time - 11:10 PM
    // H 
    // yi <= H & y(i + 1) >= H
    // yi >= H & y(i + 1) <= H
    // lazy segment tree
    // 
    int n, m; cin >> n >> m;
    vector<int> v(n);
    //while (s =) s <<= 1;
    seg = vector<int>((1 << 21));
    for (int i = 0; i < n; ++i) cin >> v[i];
    for (int i = 0; i < n - 1; ++i) {
        modify(min(v[i], v[i + 1]), max(v[i], v[i + 1]), 0, s - 1, 0, 1);
    }
    while (m--) {
        int tp; cin >> tp;
        if (tp == 1) {
            int pos, val; cin >> pos >> val;
            --pos;
            if (pos) {
                modify(min(v[pos], v[pos - 1]), max(v[pos], v[pos - 1]), 0, s - 1, 0, -1);
                modify(min(val, v[pos - 1]), max(val, v[pos - 1]), 0, s - 1, 0, 1);
            }
            if (pos < n - 1) {
                modify(min(v[pos], v[pos + 1]), max(v[pos], v[pos + 1]), 0, s - 1, 0, -1);
                modify(min(val, v[pos + 1]), max(val, v[pos + 1]), 0, s - 1, 0, 1);
            }
            v[pos] = val;

        }
        else {
            int h; cin >> h;
            cout << get(0, s - 1, 0, h) << "\n";
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    //int t; cin >> t;
    //while (t--)	
    solve();
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8516 KB Output is correct
2 Correct 5 ms 8520 KB Output is correct
3 Correct 5 ms 8524 KB Output is correct
4 Correct 5 ms 8532 KB Output is correct
5 Correct 6 ms 8536 KB Output is correct
6 Correct 6 ms 8524 KB Output is correct
7 Correct 6 ms 8524 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8516 KB Output is correct
2 Correct 5 ms 8520 KB Output is correct
3 Correct 5 ms 8524 KB Output is correct
4 Correct 5 ms 8532 KB Output is correct
5 Correct 6 ms 8536 KB Output is correct
6 Correct 6 ms 8524 KB Output is correct
7 Correct 6 ms 8524 KB Output is correct
8 Correct 44 ms 9804 KB Output is correct
9 Correct 90 ms 11168 KB Output is correct
10 Correct 89 ms 11196 KB Output is correct
11 Correct 37 ms 9788 KB Output is correct
12 Correct 73 ms 10824 KB Output is correct
13 Correct 70 ms 10952 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8516 KB Output is correct
2 Correct 5 ms 8520 KB Output is correct
3 Correct 5 ms 8524 KB Output is correct
4 Correct 5 ms 8532 KB Output is correct
5 Correct 6 ms 8536 KB Output is correct
6 Correct 6 ms 8524 KB Output is correct
7 Correct 6 ms 8524 KB Output is correct
8 Correct 44 ms 9804 KB Output is correct
9 Correct 90 ms 11168 KB Output is correct
10 Correct 89 ms 11196 KB Output is correct
11 Correct 37 ms 9788 KB Output is correct
12 Correct 73 ms 10824 KB Output is correct
13 Correct 70 ms 10952 KB Output is correct
14 Correct 172 ms 11096 KB Output is correct
15 Correct 163 ms 11096 KB Output is correct
16 Correct 186 ms 11040 KB Output is correct
17 Correct 175 ms 11072 KB Output is correct
18 Correct 159 ms 11056 KB Output is correct