oj.uz

Submission #593414

# Submission time Handle Problem Language Result Execution time Memory
593414 2022-07-11T06:20:07 Z saayan007 Simple game (IZhO17_game) C++14
100 / 100
 115 ms 34624 KB 
#include <bits/stdc++.h>
using namespace std;

/* higher types */
typedef long long ll;
typedef long double ld;

/* pairs */
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<double, double> pd;
typedef pair<ld, ld> pld;

/* vectors */
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef vector<ld> vld;
typedef vector<string> vs;
typedef vector<bool> vb;

typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<pd> vpd;
typedef vector<pld> vpld;

/* 2d vectors */
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<vd> vvd;
typedef vector<vld> vvld;
typedef vector<vs> vvs;
typedef vector<vb> vvb;

/* initialisation */
#define initvvi(mat, n, x) for(auto u : mat) u = vi(n, x);
#define initvvl(mat, n, x) for(auto u : mat) u = vl(n, x);
#define initvvb(mat, n, x) for(auto u : mat) u = vb(n, x);
#define initvvd(mat, n, x) for(auto u : mat) u = vd(n, x);
#define initvvs(mat, n, x) for(auto u : mat) u = vs(n, x);

/* loops */
#define fur(i, a, b) for(ll i = a; i <= (ll)b; ++i)
#define ruf(i, a, b) for(ll i = a; i >= (ll)b; --i)
#define each(u, v) for(auto u : v )

/* input */
#define rv(v) for(auto &u : v) cin >> u;
#define rm(mat, m) for(ll j = 0; j <= (ll)(m-1)) for(auto u : mat[j]) cin >> u;

/* output */
#define pv(v) for(auto x : v) cout << x << ' '; cout << nl;
#define pm(m) for(auto n : m) pv(n);

/* shortforms */
#define fr first 
#define sc second
#define pb push_back

#define nl "\n"
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

/* constants */
const ll infl = numeric_limits<long long int>::max();
const int infi = numeric_limits<int>::max();
const int modi = 1e9 + 7;
const ll modl = 1e9 + 7;

ll n, m;
vl y;
vl seg(4000000 + 2, 0);

void add(ll increment, ll node)
{
    node += 2000000;
    seg[node] += increment;
    for(node /= 2; node >= 1; node /= 2)
        seg[node] = seg[2*node] + seg[2*node+1];
}

ll sum(ll a, ll b)
{
    a += 2000000;
    b += 2000000;
    ll s = 0;
    while(a <= b)
    {
        if(a%2 == 1) s+= seg[a++];
        if(b%2 == 0) s+= seg[b--];
        a /= 2;
        b /= 2;
    }
    return s;
}

void remove_line(ll a, ll b)
{
    if(a > b)
        swap(a, b);
    add(-1, a + 1);
    add(1, b);
}

void add_line(ll a, ll b)
{
    if(a > b)
        swap(a, b);
    add(1, a + 1);
    add(-1, b);
}

void solve()
{
    cin >> n >> m;
    y.resize(n + 1);

    cin >> y[1];
    fur(i, 2, n)
    {
        cin >> y[i];
        add_line(y[i], y[i-1]);
    }

    while(m--)
    {
        int type;
        cin >> type;
        if(type == 2)
        {
            ll h;
            cin >> h;
            cout << sum(1, h) << nl;
            continue;
        }
        
        ll i, h;
        cin >> i >> h;
        if(i != 1)
        {
            remove_line(y[i], y[i-1]);
            add_line(h, y[i-1]);
        }
        if(i != n)
        {
            remove_line(y[i], y[i+1]);
            add_line(h, y[i+1]);
        }
        y[i] = h;
    }
}

int main() 
{
    
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

	ll t = 1;
    /* cin >> t; */
    while(t--)
    {
        solve();
    }
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31544 KB Output is correct
2 Correct 14 ms 31528 KB Output is correct
3 Correct 15 ms 31660 KB Output is correct
4 Correct 14 ms 31572 KB Output is correct
5 Correct 14 ms 31572 KB Output is correct
6 Correct 15 ms 31652 KB Output is correct
7 Correct 16 ms 31660 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31544 KB Output is correct
2 Correct 14 ms 31528 KB Output is correct
3 Correct 15 ms 31660 KB Output is correct
4 Correct 14 ms 31572 KB Output is correct
5 Correct 14 ms 31572 KB Output is correct
6 Correct 15 ms 31652 KB Output is correct
7 Correct 16 ms 31660 KB Output is correct
8 Correct 43 ms 33292 KB Output is correct
9 Correct 79 ms 34564 KB Output is correct
10 Correct 77 ms 34584 KB Output is correct
11 Correct 42 ms 33232 KB Output is correct
12 Correct 56 ms 34380 KB Output is correct
13 Correct 65 ms 34380 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31544 KB Output is correct
2 Correct 14 ms 31528 KB Output is correct
3 Correct 15 ms 31660 KB Output is correct
4 Correct 14 ms 31572 KB Output is correct
5 Correct 14 ms 31572 KB Output is correct
6 Correct 15 ms 31652 KB Output is correct
7 Correct 16 ms 31660 KB Output is correct
8 Correct 43 ms 33292 KB Output is correct
9 Correct 79 ms 34564 KB Output is correct
10 Correct 77 ms 34584 KB Output is correct
11 Correct 42 ms 33232 KB Output is correct
12 Correct 56 ms 34380 KB Output is correct
13 Correct 65 ms 34380 KB Output is correct
14 Correct 111 ms 34516 KB Output is correct
15 Correct 108 ms 34532 KB Output is correct
16 Correct 115 ms 34612 KB Output is correct
17 Correct 109 ms 34624 KB Output is correct
18 Correct 109 ms 34588 KB Output is correct