Submission #689936

#	Time	Username	Problem	Language	Result	Execution time	Memory
689936		YENGOYAN	Simple game (IZhO17_game)	C++17	100 / 100	186 ms	11196 KiB

game

/*
        //\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\\
        \\                                    //
        //  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 / 22
• Subtask 2: 27 / 27
• Subtask 3: 51 / 51