oj.uz

Submission #157251

# Submission time Handle Problem Language Result Execution time Memory
157251 2019-10-10T08:29:08 Z dandrozavr Simple game (IZhO17_game) C++14
100 / 100
 344 ms 19576 KB 
/*
Uruchamiamy samolot zwiadowczy ( + 500% do wzlamaniej )

/▄/  /█/  /◐/   /▐/   /▌/ /▀/ /░/ /🔥/   choose  own style!

***IT'S OUR LONG WAY TO THE OIILLLL***

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░▌░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░◐◐◐█████████▀▀▀▀▀▀🔥░░░░░░░░███░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░▌░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░█▌░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▄▄▀██████████████████████████████████████████████████
░░░░░░░░░░░░░░░░░░░░░░░░░░▄▄▄████▄████████ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ █████
░░░░░░░░░░░░░░░░░░░░░░░░░░░▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀█████████▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░◐◐◐█████████▀▀▀▀▀▀🔥░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████░░░░░░░░░░░░░░░
*/


//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
//#pragma comment(linker, "/stack:200000000")

#include <bits/stdc++.h>
using namespace std;



#define pb push_back
#define ll long long
#define ld long double
#define fi first
#define se second
#define eb emplace_back
#define pii pair < int , int >
#define pipii pair< int, pair < int , int > >
#define TIME clock() * 1.0 / CLOCKS_PER_SEC
mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());

//#include <ext/pb_ds/detail/standard_policies.hpp>'
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;template <typename T> using ordered_set = tree <T, null_type, less< T >, rb_tree_tag,tree_order_statistics_node_update>;
namespace fastio {template <class T> ostream &operator<<(ostream &os, const vector<T> &container){for (auto &u : container)os << u << " ";return os;}template<class T1, class T2> ostream& operator << (ostream& os, const pair<T1, T2>& p) { return os << p.first << " " << p.second; }template <class T> ostream &operator<<(ostream &os, set<T> const& con) { for (auto &u : con) os << u << " "; return os; }void pr() {}template <typename T, typename... args> void pr(T x, args... tail) { cout << x << " "; pr(tail...);}}using namespace fastio;

const int N = 1e5 + 5;
const int MA = 1e6 + 1;

const int X[4] = {0, 0, 1, -1};
const int Y[4] = {-1, 1, 0, 0};

int t[MA * 4], add[MA * 4];

void push(int v, int tl, int tr)
{
    t[v] += add[v];
    if (tl != tr)
    {
        add[v << 1] += add[v];
        add[v << 1 | 1] += add[v];
    }
    add[v] = 0;
}

void ad(int v, int tl, int tr, int l, int r, int val)
{
    if (add[v])
        push(v, tl, tr);
    if (l > r)
        return;
    if (tl == l && tr == r)
    {
        add[v] += val;
        push(v, tl, tr);
        return;
    }
    int tm = (tl + tr) >> 1;
    ad(v << 1, tl, tm, l, min(tm, r), val);
    ad(v << 1 | 1, tm + 1, tr, max(tm + 1, l), r, val);
}

int solve(int v, int tl, int tr, int pos)
{
    if (add[v])
        push(v, tl, tr);
    if (tl == tr)
        return t[v];
    int tm =(tl + tr) >> 1;
    if (pos <= tm)
        return solve(v << 1, tl, tm, pos);
        return solve(v << 1 | 1, tm + 1, tr, pos);
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Estb_probitie
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif

    int n, m;
    cin >> n >> m;
    int a[n];

    for (int i = 0; i < n; ++i)
        cin >> a[i];

    for (int i = 1; i < n; ++i)
        ad(1, 1, 1e6, min(a[i], a[i - 1]), max(a[i - 1], a[i]), 1);

    for (int i = 0; i < m; ++i)
    {
        int ty;
        cin >> ty;
        if (ty == 1)
        {
            int pos, val;
            cin >> pos >> val;
            --pos;
            for (int i = -1; i <= 1; i += 2)
            {
                if (pos)
                  ad(1, 1, 1e6, min(a[pos - 1], a[pos]), max(a[pos - 1], a[pos]), i);
                if (pos + 1 < n)
                  ad(1, 1, 1e6, min(a[pos], a[pos + 1]), max(a[pos], a[pos + 1]), i);
                a[pos] = val;
            }
        } else
        {
            int h;
            cin >> h;
            cout << solve(1, 1, 1e6, h)  << '\n';
        }
    }

}

Compilation message

game.cpp: In function 'int solve(int, int, int, int)':
game.cpp:96:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if (pos <= tm)
     ^~
game.cpp:98:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
         return solve(v << 1 | 1, tm + 1, tr, pos);
         ^~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 17 ms 15096 KB Output is correct
3 Correct 16 ms 14712 KB Output is correct
4 Correct 19 ms 14840 KB Output is correct
5 Correct 17 ms 15096 KB Output is correct
6 Correct 17 ms 14968 KB Output is correct
7 Correct 12 ms 12792 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 17 ms 15096 KB Output is correct
3 Correct 16 ms 14712 KB Output is correct
4 Correct 19 ms 14840 KB Output is correct
5 Correct 17 ms 15096 KB Output is correct
6 Correct 17 ms 14968 KB Output is correct
7 Correct 12 ms 12792 KB Output is correct
8 Correct 60 ms 1744 KB Output is correct
9 Correct 164 ms 19420 KB Output is correct
10 Correct 164 ms 19328 KB Output is correct
11 Correct 56 ms 1580 KB Output is correct
12 Correct 97 ms 3340 KB Output is correct
13 Correct 86 ms 19192 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 17 ms 15096 KB Output is correct
3 Correct 16 ms 14712 KB Output is correct
4 Correct 19 ms 14840 KB Output is correct
5 Correct 17 ms 15096 KB Output is correct
6 Correct 17 ms 14968 KB Output is correct
7 Correct 12 ms 12792 KB Output is correct
8 Correct 60 ms 1744 KB Output is correct
9 Correct 164 ms 19420 KB Output is correct
10 Correct 164 ms 19328 KB Output is correct
11 Correct 56 ms 1580 KB Output is correct
12 Correct 97 ms 3340 KB Output is correct
13 Correct 86 ms 19192 KB Output is correct
14 Correct 316 ms 19328 KB Output is correct
15 Correct 316 ms 19472 KB Output is correct
16 Correct 344 ms 19548 KB Output is correct
17 Correct 310 ms 19500 KB Output is correct
18 Correct 312 ms 19576 KB Output is correct