oj.uz

Submission #46892

# Submission time Handle Problem Language Result Execution time Memory
46892 2018-04-24T14:49:22 Z qoo2p5 Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 445 ms 69656 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int INF = (int) 1e9 + 1e6;
const ll LINF = (ll) 1e18 + 1e9;
const ll MOD = (ll) 1e9 + 7;

#define sz(x) (int) (x).size()
#define mp(x, y) make_pair(x, y)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lb(s, t, x) (int) (lower_bound(s, t, x) - s)
#define ub(s, t, x) (int) (upper_bound(s, t, x) - s)
#define rep(i, f, t) for (auto i = f; i < t; ++(i))
#define per(i, f, t) for (auto i = (f); i >= (t); --(i))

ll power(ll x, ll y, ll mod = MOD) {
    if (y == 0) {
        return 1;
    }
    if (y & 1) {
        return power(x, y - 1, mod) * x % mod;
    } else {
        ll tmp = power(x, y / 2, mod);
        return tmp * tmp % mod;
    }
}

template<typename A, typename B> bool mini(A &x, const B &y) {
    if (y < x) {
        x = y;
        return true;
    }
    return false;
}

template<typename A, typename B> bool maxi(A &x, const B &y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

void add(ll &x, ll y) {
    x += y;
    if (x >= MOD) x -= MOD;
    if (x < 0) x += MOD;
}

void run();

#define TASK ""

int main() {
#ifdef LOCAL
    if (strlen(TASK) > 0) {
        cerr << "Reminder: you are using file i/o, filename: " TASK "!" << endl << endl;
    }
#endif
#ifndef LOCAL
    if (strlen(TASK)) {
        freopen(TASK ".in", "r", stdin);
        freopen(TASK ".out", "w", stdout);
    }
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#endif
    cout << fixed << setprecision(12);
    run();
    return 0;
}

// == SOLUTION == //

const int N = 1 << 17;

struct Node {
	ll mx, sum;
};

Node t[2 * N];

void recalc(int i) {
	t[i].mx = max(t[2 * i].mx, t[2 * i + 1].mx);
	t[i].sum = t[2 * i].sum + t[2 * i + 1].sum;
}

void upd(int i, ll v) {
	i += N;
	t[i].mx = t[i].sum = v;
	i /= 2;
	while (i > 0) {
		recalc(i);
		i /= 2;
	}
}

ll get(int i, int tl, int tr, int l, int r) {
	if (tl >= r || tr <= l) {
		return 0;
	}
	if (l <= tl && tr <= r) {
		return t[i].sum;
	}
	int tm = (tl + tr) / 2;
	return get(2 * i, tl, tm, l, r) + get(2 * i + 1, tm, tr, l, r);
}

int n, q, k;

void op(int i, int tl, int tr, int l, int r) {
	if (tl >= r || tr <= l || k == 1) {
		return;
	}
	int tm = (tl + tr) / 2;
	if (l <= tl && tr <= r) {
		if (t[i].mx == 0) {
			return;
		}
		if (tl == tr - 1) {
			t[i].mx /= k;
			t[i].sum /= k;
			return;
		} else {
			op(2 * i, tl, tm, l, r);
			op(2 * i + 1, tm, tr, l, r);
		}
	} else {
		op(2 * i, tl, tm, l, r);
		op(2 * i + 1, tm, tr, l, r);
	}
	recalc(i);
}

void run() {
	cin >> n >> q >> k;
	rep(i, 1, n + 1) {
		ll x;
		cin >> x;
		upd(i, x);
	}
	while (q--) {
		int tp;
		cin >> tp;
		if (tp == 1) {
			int a, b;
			cin >> a >> b;
			upd(a, b);
		} else if (tp == 2) {
			int l, r;
			cin >> l >> r;
			op(1, 0, N, l, r + 1);
		} else {
			int l, r;
			cin >> l >> r;
			cout << get(1, 0, N, l, r + 1) << "\n";
		}
	}
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:67:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(TASK ".in", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:68:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(TASK ".out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 3 ms 676 KB Output is correct
3 Correct 3 ms 780 KB Output is correct
4 Correct 8 ms 780 KB Output is correct
5 Correct 8 ms 980 KB Output is correct
6 Correct 6 ms 980 KB Output is correct
7 Correct 7 ms 1004 KB Output is correct
8 Correct 9 ms 1072 KB Output is correct
9 Correct 8 ms 1272 KB Output is correct
10 Correct 7 ms 1272 KB Output is correct
11 Correct 7 ms 1456 KB Output is correct
12 Correct 8 ms 1556 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 5448 KB Output is correct
2 Correct 52 ms 6564 KB Output is correct
3 Correct 53 ms 9620 KB Output is correct
4 Correct 67 ms 12308 KB Output is correct
5 Correct 76 ms 14940 KB Output is correct
6 Correct 76 ms 17392 KB Output is correct
7 Correct 82 ms 19872 KB Output is correct
8 Correct 75 ms 22352 KB Output is correct
9 Correct 70 ms 24704 KB Output is correct
10 Correct 97 ms 26932 KB Output is correct
11 Correct 69 ms 29248 KB Output is correct
12 Correct 82 ms 31648 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 31648 KB Output is correct
2 Correct 23 ms 31648 KB Output is correct
3 Correct 29 ms 31648 KB Output is correct
4 Correct 68 ms 31648 KB Output is correct
5 Correct 96 ms 34928 KB Output is correct
6 Correct 93 ms 36480 KB Output is correct
7 Correct 68 ms 38016 KB Output is correct
8 Correct 106 ms 39408 KB Output is correct
9 Correct 87 ms 40640 KB Output is correct
10 Correct 82 ms 41784 KB Output is correct
11 Correct 83 ms 43072 KB Output is correct
12 Correct 83 ms 44344 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 44596 KB Output is correct
2 Correct 162 ms 46260 KB Output is correct
3 Correct 195 ms 47040 KB Output is correct
4 Correct 201 ms 48592 KB Output is correct
5 Correct 215 ms 53060 KB Output is correct
6 Correct 250 ms 55552 KB Output is correct
7 Correct 204 ms 58004 KB Output is correct
8 Correct 315 ms 60468 KB Output is correct
9 Correct 270 ms 62920 KB Output is correct
10 Correct 309 ms 65092 KB Output is correct
11 Correct 217 ms 67396 KB Output is correct
12 Correct 445 ms 69656 KB Output is correct