oj.uz

답안 #331552

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
331552 2020-11-28T22:08:54 Z jovan_b Simple game (IZhO17_game) C++17
100 / 100
 236 ms 17900 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
const int MAX = 1000000;
 
int h[MAX+5];
 
struct segment{
    int val, lazy;
} seg[4*MAX+5];
 
void propagate(int node, int l, int r){
    seg[node].val += seg[node].lazy;
    if(l == r){
        seg[node].lazy = 0;
        return;
    }
    seg[node*2].lazy += seg[node].lazy;
    seg[node*2+1].lazy += seg[node].lazy;
    seg[node].lazy = 0;
}
 
void upd(int node, int l, int r, int tl, int tr, int val){
    if(l > tr || tl > r) return;
    if(tl <= l && r <= tr){
        seg[node].lazy += val;
        return;
    }
    int mid = (l+r)/2;
    upd(node*2, l, mid, tl, tr, val);
    upd(node*2+1, mid+1, r, tl, tr, val);
}
 
int query(int node, int l, int r, int x){
    propagate(node, l, r);
    if(l == r) return seg[node].val;
    int mid = (l+r)/2;
    if(x <= mid) return query(node*2, l, mid, x);
    return query(node*2+1, mid+1, r, x);
}
 
int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
	cout.precision(10);
	cout << fixed;
 
    int n, m;
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        cin >> h[i];
    }
    for(int i=2; i<=n; i++){
        upd(1, 1, MAX, min(h[i-1], h[i]), max(h[i-1], h[i]), 1);
    }
    while(m--){
        int t;
        cin >> t;
        if(t == 1){
            int i, y;
            cin >> i >> y;
            if(i > 1) upd(1, 1, MAX, min(h[i-1], h[i]), max(h[i-1], h[i]), -1);
            if(i < n) upd(1, 1, MAX, min(h[i+1], h[i]), max(h[i+1], h[i]), -1);
            h[i] = y;
            if(i > 1) upd(1, 1, MAX, min(h[i-1], h[i]), max(h[i-1], h[i]), 1);
            if(i < n) upd(1, 1, MAX, min(h[i+1], h[i]), max(h[i+1], h[i]), 1);
        }
        else{
            int y;
            cin >> y;
            cout << query(1, 1, MAX, y) << "\n";
        }
    }
    return 0;
}

Subtask #1
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 8 ms 11628 KB Output is correct
3 Correct 8 ms 11244 KB Output is correct
4 Correct 8 ms 11500 KB Output is correct
5 Correct 8 ms 11500 KB Output is correct
6 Correct 8 ms 11628 KB Output is correct
7 Correct 6 ms 9708 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 8 ms 11628 KB Output is correct
3 Correct 8 ms 11244 KB Output is correct
4 Correct 8 ms 11500 KB Output is correct
5 Correct 8 ms 11500 KB Output is correct
6 Correct 8 ms 11628 KB Output is correct
7 Correct 6 ms 9708 KB Output is correct
8 Correct 58 ms 1004 KB Output is correct
9 Correct 127 ms 17792 KB Output is correct
10 Correct 127 ms 17772 KB Output is correct
11 Correct 55 ms 1004 KB Output is correct
12 Correct 80 ms 1900 KB Output is correct
13 Correct 72 ms 17900 KB Output is correct

Subtask #3
51.0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 8 ms 11628 KB Output is correct
3 Correct 8 ms 11244 KB Output is correct
4 Correct 8 ms 11500 KB Output is correct
5 Correct 8 ms 11500 KB Output is correct
6 Correct 8 ms 11628 KB Output is correct
7 Correct 6 ms 9708 KB Output is correct
8 Correct 58 ms 1004 KB Output is correct
9 Correct 127 ms 17792 KB Output is correct
10 Correct 127 ms 17772 KB Output is correct
11 Correct 55 ms 1004 KB Output is correct
12 Correct 80 ms 1900 KB Output is correct
13 Correct 72 ms 17900 KB Output is correct
14 Correct 234 ms 17516 KB Output is correct
15 Correct 236 ms 17516 KB Output is correct
16 Correct 227 ms 17516 KB Output is correct
17 Correct 232 ms 17516 KB Output is correct
18 Correct 233 ms 17644 KB Output is correct