oj.uz

답안 #758053

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
758053 2023-06-14T05:57:55 Z vjudge1 Simple game (IZhO17_game) C++17
49 / 100
 255 ms 22540 KB 
#include"bits/stdc++.h"
using namespace std;
#define ll long long
const ll mod = 1000000007;

int N, Left, Right, pos, val;
int ans[1000001], seg[5000000], lazy[5000000];

void spread(int ind) {
    seg[ind * 2] += lazy[ind];
    seg[ind * 2 + 1] += lazy[ind];
    lazy[ind * 2] += lazy[ind];
    lazy[ind * 2 + 1] += lazy[ind];
    lazy[ind] = 0;
}

void update(int l = 1, int r = N, int ind = 1) {
    if(l > Right || r < Left)
        return;
    if(l != r)
        spread(ind);
    if(l >= Left && r <= Right) {
        lazy[ind] += val;
        seg[ind] += val;
        return;
    }
    int mid = (l + r) / 2;
    update(l, mid, ind * 2);
    update(mid + 1, r, ind * 2 + 1);
    seg[ind] = seg[ind * 2] + seg[ind * 2 + 1];
}

int get_ans(int l = 1, int r = N, int ind = 1) {
    if(l > pos || r < pos)
        return 0;
    if(l == r)
        return seg[ind];
    spread(ind);
    int mid = (l + r) / 2;
    return get_ans(l, mid, ind * 2) + get_ans(mid + 1, r, ind * 2 + 1);
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int n, m;
    cin >> n >> m;
    int h[n + 1];
    N = exp2(ceil(log2(1000000)));
    for(int i = 1; i <= n; i++) {
        cin >> h[i];
        ans[h[i]]++;
    }
    for(int i = 1; i < n; i++) {
        Left = min(h[i], h[i + 1]);
        Right = h[i] + h[i + 1] - Left;
        Left++, Right--;
        if(Left > Right)
            continue;
        val = 1;
        update();
    }
    while(m--) {
        int type;
        cin >> type;
        if(type == 1) {
            int ind, new_h;
            cin >> ind >> new_h;
            ans[h[ind]]--;
            for(int i = max(ind - 1, 1); i <= min(ind, n - 1); i++) {
                Left = min(h[i], h[i + 1]);
                Right = h[i] + h[i + 1] - Left;
                Left++, Right--;
                if(Left > Right)
                    continue;
                val = -1;
                update();
            }
            h[ind] = new_h;
            for(int i = max(ind - 1, 1); i <= min(ind, n - 1); i++) {
                Left = min(h[i], h[i + 1]);
                Right = h[i] + h[i + 1] - Left;
                Left++, Right--;
                if(Left > Right)
                    continue;
                val = 1;
                update();
            }
        }
        else if(type == 2) {
            cin >> pos;
            cout << ans[pos] + get_ans() << "\n";
        }
    }

    return 0;
}

Subtask #1
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 14 ms 17428 KB Output is correct
3 Correct 11 ms 17020 KB Output is correct
4 Correct 13 ms 17340 KB Output is correct
5 Correct 10 ms 17364 KB Output is correct
6 Correct 10 ms 17364 KB Output is correct
7 Correct 7 ms 12444 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 14 ms 17428 KB Output is correct
3 Correct 11 ms 17020 KB Output is correct
4 Correct 13 ms 17340 KB Output is correct
5 Correct 10 ms 17364 KB Output is correct
6 Correct 10 ms 17364 KB Output is correct
7 Correct 7 ms 12444 KB Output is correct
8 Correct 58 ms 1716 KB Output is correct
9 Correct 145 ms 22444 KB Output is correct
10 Correct 160 ms 22480 KB Output is correct
11 Correct 36 ms 1692 KB Output is correct
12 Correct 96 ms 3320 KB Output is correct
13 Correct 138 ms 18464 KB Output is correct

Subtask #3
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 14 ms 17428 KB Output is correct
3 Correct 11 ms 17020 KB Output is correct
4 Correct 13 ms 17340 KB Output is correct
5 Correct 10 ms 17364 KB Output is correct
6 Correct 10 ms 17364 KB Output is correct
7 Correct 7 ms 12444 KB Output is correct
8 Correct 58 ms 1716 KB Output is correct
9 Correct 145 ms 22444 KB Output is correct
10 Correct 160 ms 22480 KB Output is correct
11 Correct 36 ms 1692 KB Output is correct
12 Correct 96 ms 3320 KB Output is correct
13 Correct 138 ms 18464 KB Output is correct
14 Incorrect 255 ms 22540 KB Output isn't correct
15 Halted 0 ms 0 KB -