Submission #593414

#	Time	Username	Problem	Language	Result	Execution time	Memory
593414		saayan007	Simple game (IZhO17_game)	C++14	100 / 100	115 ms	34624 KiB

game

#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 / 22
• Subtask 2: 27 / 27
• Subtask 3: 51 / 51