PCMS2 Web Client

Information Statements Monitor Submit Runs Messenger Logout

Run source

Problem E. RMQ2
Attempt 9
Time    10:23:33
Outcome OK
Language    MinGW C++11 4.8
Source
?
#include <bits/stdc++.h>

#define ll long long
#define str string
#define XX first
#define YY second
#define vec vector
#define re return
#define y1 dasfasdf32s23s3224
#define LN '\n'
#define all(a) a.begin(), a.end()
#define in insert
#define pb push_back
#define mp make_pair
#define forn(i, n) for (int i = 0; i < n; i++)
#define form(i, a, b) for (int i = a; i <= b; i++)

const int INF = 1e9 + 7;
const ll LINF = 1e18 + 7;
const ll P = 997;
const ll nothing = LINF + 1;
const int MOD = 1e9 + 7;
const int MOD1 = 1e9 + 7;
const int MOD2 = 1e9 + 5;
const bool is_testing = 0;
const int MAXN = 50000;

using namespace std;

int n, maxk;
ll t[800007], a[100007], p[800007], u[800007];

void push(int v)
{
    if (v > maxk)
        return;
    if (u[v] == nothing)
    {
        t[v] += p[v];
        if (u[2 * v + 1] != nothing)
            push(2 * v + 1);
        if (u[2 * v + 2] != nothing)
            push(2 * v + 2);
        p[2 * v + 1] += p[v];
        p[2 * v + 2] += p[v];
        p[v] = 0;
    }
    else
    {
        t[v] = u[v];
        u[2 * v + 1] = u[v];
        u[2 * v + 2] = u[v];
        p[2 * v + 1] = 0;
        p[2 * v + 2] = 0;
        p[v] = 0;
        u[v] = nothing;
    }
}
void build(int v, int vl, int vr)
{
    maxk = max(maxk, v);
    if (vl == vr)
        t[v] = a[vl];
    else
    {
        int vm = (vl + vr) / 2;
        build(v * 2 + 1, vl, vm);
        build(v * 2 + 2, vm + 1, vr);
        t[v] = min(t[v * 2 + 1], t[v * 2 + 2]);
    }
}

ll get(int v, int vl, int vr, int l, int r)
{
    push(v);
    if (l > vr || r < vl)
        re LINF;
    if (vl >= l && vr <= r)
        re t[v];
    int vm = (vl + vr) / 2;
    ll q1 = get(v * 2 + 1, vl, vm, l, r);
    ll q2 = get(v * 2 + 2, vm + 1, vr, l, r);
    re min(q1, q2);
}

void add(int v, int vl, int vr, int l, int r, ll x)
{
    push(v);
    if (vl > r || vr < l)
        return;
    if (vl >= l && vr <= r)
    {
        p[v] += (ll)x;
        push(v);
    }
    else
    {
        int vm = (vl + vr) / 2;
        add(v * 2 + 1, vl, vm, l, r, x);
        add(v * 2 + 2, vm + 1, vr, l, r, x);
        t[v] = min(t[2 * v + 1], t[2 * v + 2]);
    }
}

void iz(int v, int vl, int vr, int l, int r, ll x)
{
    push(v);
    if (vr < l || vl > r)
        return;
    if (vl >= l && vr <= r)
    {
        u[v] = x;
        push(v);
    }
    else
    {
        int vm = (vl + vr) / 2;
        iz(v * 2 + 1, vl, vm, l, r, x);
        iz(v * 2 + 2, vm + 1, vr, l, r, x);
        t[v] = min(t[v * 2 + 1], t[v * 2 + 2]);
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie();
    freopen("rmq2.in", "r", stdin);
    freopen("rmq2.out", "w", stdout);
    if (is_testing)
    {
        freopen("input.txt", "r", stdin);
    }
    cin >> n;
    forn(i, n)
        cin >> a[i];
    forn(i, 800005)
        u[i] = nothing;
    build(0, 0, n - 1);
    str s;
    while(cin >> s)
    {
        if (s == "min")
        {
            int l, r;
            cin >> l >> r;
            l--; r--;
            cout << get(0, 0, n - 1, l, r) << LN;
        }
        else
        if (s == "add")
        {
            ll l, r, x;
            cin >> l >> r >> x;
            l--; r--;
            add(0, 0, n - 1, l, r, x);
        }
        else
        {
            ll l, r, x;
            cin >> l >> r >> x;
            l--; r--;
            iz(0, 0, n - 1, l, r, x);
        }
    /*
    forn(i, 2 * n)
        cout << t[i] << ' ';
    cout << LN;*/
    }
}