oj.uz

Submission #167968

# Submission time Handle Problem Language Result Execution time Memory
167968 2019-12-11T04:11:52 Z Rakhmand Simple game (IZhO17_game) C++14
100 / 100
 226 ms 11264 KB 
//
//  ROIGold.cpp
//  Main calisma
//
//  Created by Rakhman on 05/02/2019.
//  Copyright © 2019 Rakhman. All rights reserved.
//
 
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <iterator>
 
#define ios ios_base::sync_with_stdio(0), cout.tie(0), cin.tie(0);
#define S second
#define F first
#define pb push_back
#define nl '\n'
#define NL cout << '\n';
#define EX exit(0)
#define all(s) s.begin(), s.end()
#define no_answer return cout << 0, 0;
#define FOR(i, start, finish, k) for(int i = start; i <= finish; i += k)
 
const int MXN = 1e6 + 200;
const long long MNN = 4e2 + 200;
const long long MOD = 1e9 + 7;
const long long INF = 1e18;
const int OO = 1e9 + 500;
 
typedef long long llong;
typedef unsigned long long ullong;
 
using namespace std;
 
int n, m, h[MXN], t[MXN * 4], mod[MXN * 4];

void upd(int v, int tl, int tr, int ind, int x){
    if(tl == tr){
        t[v] += x;
        return ;
    }
    int tm = (tl + tr) / 2;
    if(ind <= tm){
        upd(v + v, tl, tm, ind, x);
    }else{
        upd(v + v + 1, tm + 1, tr, ind, x);
    }
    t[v] = t[v + v] + t[v + v + 1];
}

llong get(int v, int tl, int tr, int L, int R){
    if(L <= tl && tr <= R){
        return t[v];
    }
    if(tl > R || tr < L || L > R){
        return 0;
    }
    int tm = (tl + tr) / 2;
    return get(v + v, tl, tm, L, R) + get(v + v + 1, tm + 1, tr, L, R);
}

void del(int pos){
    if(pos > 1){
        if(h[pos - 1] > h[pos]){
            upd(1, 1, 1000000, h[pos] + 1, -1);
            upd(1, 1, 1000000, h[pos - 1], 1);
        }else if(h[pos - 1] < h[pos]){
            upd(1, 1, 1000000, h[pos - 1] + 1, -1);
            upd(1, 1, 1000000, h[pos], 1);
        }
    }
}

void add(int pos){
    if(pos > 1) {
        if(h[pos - 1] > h[pos]){
            upd(1, 1, 1000000, h[pos] + 1, 1);
            upd(1, 1, 1000000, h[pos - 1], -1);
        }else if(h[pos - 1] < h[pos]){
            upd(1, 1, 1000000, h[pos - 1] + 1, 1);
            upd(1, 1, 1000000, h[pos], -1);
        }
    }
}

int main () {
    ios;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> h[i];
        add(i);
    }
    for(int i = 1; i <= m; i++){
        int pos, val, type, H;
        cin >> type;
        if(type == 1){
            cin >> pos >> val;
            del(pos);
            if(pos + 1 <= n) del(pos + 1);
            h[pos] = val;
            add(pos);
            if(pos + 1 <= n) add(pos + 1);
        }else{
            cin >> H;
            cout << get(1, 1, 1000000, 1, H) << nl;
        }
    }
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 9 ms 7544 KB Output is correct
3 Correct 9 ms 7288 KB Output is correct
4 Correct 10 ms 7416 KB Output is correct
5 Correct 9 ms 7416 KB Output is correct
6 Correct 9 ms 7516 KB Output is correct
7 Correct 4 ms 376 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 9 ms 7544 KB Output is correct
3 Correct 9 ms 7288 KB Output is correct
4 Correct 10 ms 7416 KB Output is correct
5 Correct 9 ms 7416 KB Output is correct
6 Correct 9 ms 7516 KB Output is correct
7 Correct 4 ms 376 KB Output is correct
8 Correct 75 ms 1812 KB Output is correct
9 Correct 136 ms 11208 KB Output is correct
10 Correct 131 ms 11264 KB Output is correct
11 Correct 57 ms 1660 KB Output is correct
12 Correct 102 ms 3068 KB Output is correct
13 Correct 92 ms 2936 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 9 ms 7544 KB Output is correct
3 Correct 9 ms 7288 KB Output is correct
4 Correct 10 ms 7416 KB Output is correct
5 Correct 9 ms 7416 KB Output is correct
6 Correct 9 ms 7516 KB Output is correct
7 Correct 4 ms 376 KB Output is correct
8 Correct 75 ms 1812 KB Output is correct
9 Correct 136 ms 11208 KB Output is correct
10 Correct 131 ms 11264 KB Output is correct
11 Correct 57 ms 1660 KB Output is correct
12 Correct 102 ms 3068 KB Output is correct
13 Correct 92 ms 2936 KB Output is correct
14 Correct 226 ms 11216 KB Output is correct
15 Correct 217 ms 11256 KB Output is correct
16 Correct 222 ms 11176 KB Output is correct
17 Correct 223 ms 11236 KB Output is correct
18 Correct 223 ms 11256 KB Output is correct