oj.uz

Submission #758093

# Submission time Handle Problem Language Result Execution time Memory
758093 2023-06-14T06:59:19 Z vjudge1 Simple game (IZhO17_game) C++17
100 / 100
 352 ms 18972 KB 
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
 
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif
 
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
 
 
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <fstream>
#define endl '\n'
#define int long long
using namespace std;

int a[100001];
int N,Right,n,Left;
int seg[3000001];


int bg = 0;
void Update(int pos, int val){
    int ind = 0;
    if(bg == 1 and pos + 1 < n){
        int aa = min(a[pos], a[pos + 1]), bb = max(a[pos], a[pos + 1]);
        seg[aa + N - 1]--;
        seg[bb + N]++;
        ind = aa + N - 1;
        while(ind/=2) seg[ind] = seg[ind * 2] + seg[ind * 2 + 1];
        ind = bb + N;
        while(ind/=2) seg[ind] = seg[ind * 2] + seg[ind * 2 + 1];
    }
    if(bg == 1 and pos - 1 >= 0){
        int aa = min(a[pos], a[pos - 1]), bb = max(a[pos], a[pos - 1]);
        seg[aa + N - 1]--;
        seg[bb + N]++;
        ind = aa + N - 1;
        while(ind/=2) seg[ind] = seg[ind * 2] + seg[ind * 2 + 1];
        ind = bb + N;
        while(ind/=2) seg[ind] = seg[ind * 2] + seg[ind * 2 + 1];
    }
    a[pos] = val;
    if(pos + 1 < n){
        int aa = min(a[pos], a[pos + 1]), bb = max(a[pos], a[pos + 1]);
        seg[aa + N - 1]++;
        seg[bb + N]--;
        ind = aa + N - 1;
        while(ind/=2) seg[ind] = seg[ind * 2] + seg[ind * 2 + 1];
        ind = bb + N;
        while(ind/=2) seg[ind] = seg[ind * 2] + seg[ind * 2 + 1];
    }
    if(bg == 1 and pos - 1 >= 0){
        int aa = min(a[pos], a[pos - 1]), bb = max(a[pos], a[pos - 1]);
        seg[aa + N - 1]++;
        seg[bb + N]--;
        ind = aa + N - 1;
        while(ind/=2) seg[ind] = seg[ind * 2] + seg[ind * 2 + 1];
        ind = bb + N;
        while(ind/=2) seg[ind] = seg[ind * 2] + seg[ind * 2 + 1];
    }
}

int Query(int l = 1, int r = N, int ind = 1){
    if(l > Right or r < Left) return 0;
    if(l >= Left and r <= Right) return seg[ind];
    int mid = (l + r) / 2;
    return Query(l, mid, ind * 2) + Query(mid + 1,r, ind * 2 + 1);
}
signed main() {
    int m; cin >> n >> m;
    
    N = exp2(ceil(log2(1e6)));
    for(int i = 0; i < n; i++)  cin >> a[i];
    for(int i = 0; i < n; i++) Update(i,a[i]);
    bg = 1;
    Left = 1;
    while(m--){
        int t; cin >> t;
        if(t == 1){
            int pos,val; cin >> pos >> val;
            Update(pos - 1, val);
        }else{
            int H; cin >> H;
            Right = H;
            cout << Query() << endl;
        }
    }
    
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 8 ms 11536 KB Output is correct
3 Correct 8 ms 11220 KB Output is correct
4 Correct 7 ms 11476 KB Output is correct
5 Correct 17 ms 11348 KB Output is correct
6 Correct 11 ms 11476 KB Output is correct
7 Correct 4 ms 340 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 8 ms 11536 KB Output is correct
3 Correct 8 ms 11220 KB Output is correct
4 Correct 7 ms 11476 KB Output is correct
5 Correct 17 ms 11348 KB Output is correct
6 Correct 11 ms 11476 KB Output is correct
7 Correct 4 ms 340 KB Output is correct
8 Correct 239 ms 1944 KB Output is correct
9 Correct 316 ms 17836 KB Output is correct
10 Correct 352 ms 17824 KB Output is correct
11 Correct 247 ms 1912 KB Output is correct
12 Correct 257 ms 2612 KB Output is correct
13 Correct 288 ms 2276 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 8 ms 11536 KB Output is correct
3 Correct 8 ms 11220 KB Output is correct
4 Correct 7 ms 11476 KB Output is correct
5 Correct 17 ms 11348 KB Output is correct
6 Correct 11 ms 11476 KB Output is correct
7 Correct 4 ms 340 KB Output is correct
8 Correct 239 ms 1944 KB Output is correct
9 Correct 316 ms 17836 KB Output is correct
10 Correct 352 ms 17824 KB Output is correct
11 Correct 247 ms 1912 KB Output is correct
12 Correct 257 ms 2612 KB Output is correct
13 Correct 288 ms 2276 KB Output is correct
14 Correct 258 ms 17544 KB Output is correct
15 Correct 280 ms 18848 KB Output is correct
16 Correct 272 ms 18960 KB Output is correct
17 Correct 278 ms 18964 KB Output is correct
18 Correct 267 ms 18972 KB Output is correct