Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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;*/
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement