oj.uz

답안 #915492

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
915492 2024-01-24T04:54:48 Z vjudge1 Simple game (IZhO17_game) C++17
100 / 100
 78 ms 13112 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

#include <bits/stdc++.h>
 
#define int long long 
#define pb push_back
#define ui unsigned int
#define ld long double
#define pl pair<long long int,  long long int>
#define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ff first    
#define ss second
#define sz size()
#define all(x) x.begin(), x.end()
 
using namespace std;
 
const int maxn = 1e6 + 11;
const int inf = 1e17 + 1;
const int mod = 1e9 + 7;
// const int mod = 998244353;
const int dx[] = {-1, 0, 0, 1, -1, -1, 1, 1};
const int dy[] = {0, -1, 1 , 0, -1, 1, -1, 1};
const double eps = 1e-10;

int n, m;
int h[maxn];
int t[maxn];

int sum(int r) {
    int cnt = 0;
    for(; r >= 1; r = (r & (r + 1)) - 1) {
        cnt += t[ r ];
    }
    return cnt;
}
void update(int pos, int val) {
    for (; pos <= maxn; pos |= (pos + 1))
        t[ pos ] += val;
}

void solve() {
    cin >> n >> m;

    for(int i = 1; i <= n; i++) {
        cin >> h[ i ];
    }
    for(int i = 1; i < n; i++) {
        update(min(h[ i ], h[i + 1]), 1);
        update(max(h[ i ], h[i + 1]), -1);
    }

    while(m--) {
        int tp;

        cin >> tp;

        if(tp == 2) {
            int x;

            cin >> x;

            cout << sum(x) << "\n";
        }
        else {
            int pos, val;

            cin >> pos >> val;

            if(pos < n) {
                update(min(h[ pos ], h[pos + 1]), -1);
                update(max(h[ pos ], h[pos + 1]), 1);
                update(min(val, h[pos + 1]), 1);
                update(max(val, h[pos + 1]), -1);
            }
            if(pos > 1) {
                update(min(h[ pos ], h[pos - 1]), -1);
                update(max(h[ pos ], h[pos - 1]), 1);
                update(min(val, h[pos - 1]), 1);
                update(max(val, h[pos - 1]), -1);
            }
            h[ pos ] = val;
        }
    }
}
    
signed main() {
    // freopen("sum.in", "r", stdin); 
    // freopen("sum.out", "w", stdout);
 
    boost;      

    int tt = 1;

    // cin >> tt;

    for(int i = 1; i <= tt; i++) {
        // cout << "Case " << i << ":\n";
        solve();    
    }           
}

Subtask #1
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 3 ms 8796 KB Output is correct
3 Correct 3 ms 8816 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 2 ms 8840 KB Output is correct
7 Correct 2 ms 6488 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 3 ms 8796 KB Output is correct
3 Correct 3 ms 8816 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 2 ms 8840 KB Output is correct
7 Correct 2 ms 6488 KB Output is correct
8 Correct 31 ms 9008 KB Output is correct
9 Correct 41 ms 12884 KB Output is correct
10 Correct 48 ms 13112 KB Output is correct
11 Correct 29 ms 9556 KB Output is correct
12 Correct 34 ms 10616 KB Output is correct
13 Correct 33 ms 10576 KB Output is correct

Subtask #3
51.0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 3 ms 8796 KB Output is correct
3 Correct 3 ms 8816 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 2 ms 8840 KB Output is correct
7 Correct 2 ms 6488 KB Output is correct
8 Correct 31 ms 9008 KB Output is correct
9 Correct 41 ms 12884 KB Output is correct
10 Correct 48 ms 13112 KB Output is correct
11 Correct 29 ms 9556 KB Output is correct
12 Correct 34 ms 10616 KB Output is correct
13 Correct 33 ms 10576 KB Output is correct
14 Correct 64 ms 12952 KB Output is correct
15 Correct 64 ms 12884 KB Output is correct
16 Correct 61 ms 12872 KB Output is correct
17 Correct 78 ms 13108 KB Output is correct
18 Correct 66 ms 13020 KB Output is correct