Submission #46892

#	Time	Username	Problem	Language	Result	Execution time	Memory
46892		qoo2p5	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	445 ms	69656 KiB

sterilizing

#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 (stderr)

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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75