oj.uz

Submission #333997

# Submission time Handle Problem Language Result Execution time Memory
333997 2020-12-08T05:13:03 Z talant117408 Simple game (IZhO17_game) C++17
100 / 100
 508 ms 18668 KB 
/*
    Code written by Talant I.D.
*/
  
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>

//using namespace __gnu_pbds;
using namespace std;

//typedef tree <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
  
#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) int((v).size())
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define OK cout << "OK" << endl;
  
inline bool isvowel(char ch){
    ch = tolower(ch);
    return (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u');
}
  
inline bool isprime(int n){
    if(n < 2 || (n%2 == 0 && n != 2)) return false;
    for(int i = 3; i*i <= n; i++)
        if(n%i == 0) return false;
    return true;
}
 
class Union{
    private:
        vector <int> saizu, link;
    public:
        Union(int n){
            saizu.assign(n, 1); link.resize(n); 
            iota(all(link), 0);
        }
        int find(int n){
            if(link[n] == n) return n;
            return link[n] = find(link[n]);
        }
        int same(int a, int b){
            return find(a) == find(b);
        }
        void unite(int a, int b){
            if(same(a, b)) return;
             
            a = find(a); b = find(b);
            if(saizu[a] < saizu[b]) swap(a, b);
             
            saizu[a] += saizu[b];
            link[b] = a;
        }
        int getsize(int a){
            return saizu[find(a)];
        }
};
 
const int mod = 1e9+7;
 
ll mode(ll a){
    a %= mod;
    if(a < 0) a += mod;
    return a;
}
 
ll subt(ll a, ll b){
    return mode(mode(a)-mode(b));
}
 
ll add(ll a, ll b){
    return mode(mode(a)+mode(b));
}
 
ll mult(ll a, ll b){
    return mode(mode(a)*mode(b));
}
 
ll binpow(ll a, ll b){
    ll res = 1;
    while(b){
        if(b&1) res = mult(res, a);
        a = mult(a, a);
        b >>= 1;
    }
    return res;
}

const int N = 1e6+7;
int tree[N*4], lz[N*4];

void push(int v, int l, int r){
    if(lz[v]){
        tree[v] += (r-l+1)*lz[v];
        if(l != r){
            lz[v*2] += lz[v];
            lz[v*2+1] += lz[v];
        }
        lz[v] = 0;
    }
}
int get(int v, int l, int r, int ql, int qr){
    push(v, l, r);
    if(l > qr || r < ql) return 0;
    if(ql <= l && r <= qr) return tree[v];
    int mid = (l+r) >> 1;
    return get(v*2, l, mid, ql, qr) + get(v*2+1, mid+1, r, ql, qr);
}
void update(int v, int l, int r, int ql, int qr, int val){
    push(v, l, r);
    if(l > qr || r < ql) return ;
    if(ql <= l && r <= qr){
        tree[v] += (r-l+1)*val;
        if(l != r){
            lz[v<<1] += val;
            lz[v*2+1] += val;
        }
        return ;
    }
    int mid = (l+r) >> 1;  
    update(v*2, l, mid, ql, qr, val);
    update(v*2+1, mid+1, r, ql, qr, val);
    tree[v] = tree[v*2] + tree[v*2+1];
}

int main(){
    do_not_disturb
    
    int n, q;
    cin >> n >> q;
    vector <int> v(n+1);
    for(int i = 1; i <= n; i++){
        cin >> v[i];
    }
    for(int i = 1; i < n; i++){
        update(1, 1, N, min(v[i], v[i+1]), max(v[i], v[i+1]), 1);
    }
    while(q--){
        int type;
        cin >> type;
        if(type == 1){
            int pos, x;
            cin >> pos >> x;
            int i = pos;
            if(i > 1)
                update(1, 1, N, min(v[i], v[i-1]), max(v[i], v[i-1]), -1);
            if(i < n)
                update(1, 1, N, min(v[i], v[i+1]), max(v[i], v[i+1]), -1);
            v[pos] = x;
            if(i > 1)
                update(1, 1, N, min(v[i], v[i-1]), max(v[i], v[i-1]), 1);
            if(i < n)
                update(1, 1, N, min(v[i], v[i+1]), max(v[i], v[i+1]), 1);
        }
        else{
            int h;
            cin >> h;
            cout << get(1, 1, N, h, h) << endl;
        }
    }
    
    return 0;
}
/* 
3 3
1 5 1
2 3
1 1 5
2 3
*/

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 15 ms 15084 KB Output is correct
3 Correct 13 ms 14828 KB Output is correct
4 Correct 15 ms 15212 KB Output is correct
5 Correct 13 ms 14956 KB Output is correct
6 Correct 14 ms 14956 KB Output is correct
7 Correct 8 ms 12908 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 15 ms 15084 KB Output is correct
3 Correct 13 ms 14828 KB Output is correct
4 Correct 15 ms 15212 KB Output is correct
5 Correct 13 ms 14956 KB Output is correct
6 Correct 14 ms 14956 KB Output is correct
7 Correct 8 ms 12908 KB Output is correct
8 Correct 84 ms 1004 KB Output is correct
9 Correct 263 ms 17772 KB Output is correct
10 Correct 239 ms 18668 KB Output is correct
11 Correct 95 ms 1676 KB Output is correct
12 Correct 146 ms 2948 KB Output is correct
13 Correct 161 ms 18668 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 15 ms 15084 KB Output is correct
3 Correct 13 ms 14828 KB Output is correct
4 Correct 15 ms 15212 KB Output is correct
5 Correct 13 ms 14956 KB Output is correct
6 Correct 14 ms 14956 KB Output is correct
7 Correct 8 ms 12908 KB Output is correct
8 Correct 84 ms 1004 KB Output is correct
9 Correct 263 ms 17772 KB Output is correct
10 Correct 239 ms 18668 KB Output is correct
11 Correct 95 ms 1676 KB Output is correct
12 Correct 146 ms 2948 KB Output is correct
13 Correct 161 ms 18668 KB Output is correct
14 Correct 508 ms 18412 KB Output is correct
15 Correct 490 ms 18412 KB Output is correct
16 Correct 480 ms 18284 KB Output is correct
17 Correct 482 ms 18412 KB Output is correct
18 Correct 484 ms 18284 KB Output is correct