oj.uz

Submission #527857

# Submission time Handle Problem Language Result Execution time Memory
527857 2022-02-18T14:01:31 Z AriaH Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 2361 ms 7744 KB 
/* I can do this all day */

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;

#define F first
#define S second
#define all(x) x.begin(),x.end()
#define Mp make_pair
#define point complex
#define endl '\n'
#define SZ(x) (int)x.size()
#define fast_io ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define file_io freopen("input.txt", "r+", stdin); freopen("output.txt", "w+", stdout);
#define mashtali return cout << "Hello, World!", 0;

const int N = 1e6 + 10;
const int LOG = 20;
const ll mod = 1e9 + 7;
const ll inf = 8e18;
const double pi = acos(-1);
const ld eps = 1e-18;
const ld one = 1.;

ll pw(ll a, ll b, ll M, ll ret = 1) { if(a == 0) return 0; a %= M; while(b) { ret = (b & 1? ret * a % M : ret), a = a * a % M, b >>= 1; } return ret % M; }

mt19937 rng(time(nullptr));

int n, q, k, A[N];

pii seg[N << 2];

ll sum[N << 2];

void build(int v = 1, int tl = 1, int tr = n)
{
	if(tl == tr)
	{
		seg[v] = {A[tl], tl};
		sum[v] = A[tl];
		return;
	}
	int mid = (tl + tr) >> 1;
	build(v << 1, tl, mid), build(v << 1 | 1, mid + 1, tr);
	seg[v] = max(seg[v << 1], seg[v << 1 | 1]);
	sum[v] = sum[v << 1] + sum[v << 1 | 1];
}

void upd(int p, int x, int v = 1, int tl = 1, int tr = n)
{
	if(tl == tr)
	{
		seg[v] = Mp(x, tl);
		sum[v] = x;
		return;
	}
	int mid = (tl + tr) >> 1;
	if(p <= mid) upd(p, x, v << 1, tl, mid);
	else upd(p, x, v << 1 | 1, mid + 1, tr);
	seg[v] = max(seg[v << 1], seg[v << 1 | 1]);
	sum[v] = sum[v << 1] + sum[v << 1 | 1];
}

ll get(int l, int r, int v = 1, int tl = 1, int tr = n)
{
	if(l > tr || r < tl || l > r) return 0;
	if(l <= tl && tr <= r) return sum[v];
	int mid = (tl + tr) >> 1;
	return get(l, r, v << 1, tl, mid) + get(l, r, v << 1 | 1, mid + 1, tr);
}

pii ask(int l, int r, int v = 1, int tl = 1, int tr = n)
{
	if(l > tr || r < tl || l > r) return {-1, -1};
	if(l <= tl && tr <= r)
	{
		return seg[v];
	}
	int mid = (tl + tr) >> 1;
	return max(ask(l, r, v << 1, tl, mid), ask(l, r, v << 1 | 1, mid + 1, tr)); 
}

int main()
{
	fast_io;
	cin >> n >> q >> k;
	for(int i = 1; i <= n; i ++)
	{
		cin >> A[i];
	}
	build();
	for(int j = 1; j <= q; j ++)
	{
		int tp, fir, sec;
		cin >> tp >> fir >> sec;
		if(tp == 1)
		{
			A[fir] = sec;
			upd(fir, sec);
		}
		if(tp == 2)
		{
			if(k == 1) continue;
			pii cu;
			vector < int > pos;
			while((cu = ask(fir, sec)).F > 0)
			{
				A[cu.S] /= k;
				upd(cu.S, 0);
				pos.push_back(cu.S);
			}
			for(auto x : pos)
			{
				upd(x, A[x]);
			}
		}
		if(tp == 3)
		{
			cout << get(fir, sec) << endl;
		}
		/*printf("j = %d\n", j);
		for(int i = 1; i <= n; i ++)
		{
			printf("%d ", A[i]);
		}
		printf("\n");
		*/
	}
	return 0;
}

/* check corner case(n = 1?), watch for negetive index or overflow */

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 6 ms 332 KB Output is correct
4 Correct 22 ms 432 KB Output is correct
5 Correct 24 ms 508 KB Output is correct
6 Correct 15 ms 496 KB Output is correct
7 Correct 20 ms 504 KB Output is correct
8 Correct 21 ms 516 KB Output is correct
9 Correct 27 ms 496 KB Output is correct
10 Correct 19 ms 508 KB Output is correct
11 Correct 18 ms 460 KB Output is correct
12 Correct 20 ms 512 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 4124 KB Output is correct
2 Correct 42 ms 4456 KB Output is correct
3 Correct 37 ms 6596 KB Output is correct
4 Correct 46 ms 7224 KB Output is correct
5 Correct 55 ms 7684 KB Output is correct
6 Correct 56 ms 7708 KB Output is correct
7 Correct 55 ms 7744 KB Output is correct
8 Correct 62 ms 7632 KB Output is correct
9 Correct 56 ms 7620 KB Output is correct
10 Correct 51 ms 7492 KB Output is correct
11 Correct 51 ms 7588 KB Output is correct
12 Correct 50 ms 7516 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 588 KB Output is correct
2 Correct 24 ms 2596 KB Output is correct
3 Correct 29 ms 2632 KB Output is correct
4 Correct 59 ms 1548 KB Output is correct
5 Correct 89 ms 4900 KB Output is correct
6 Correct 101 ms 5016 KB Output is correct
7 Correct 47 ms 5876 KB Output is correct
8 Correct 97 ms 6436 KB Output is correct
9 Correct 127 ms 6276 KB Output is correct
10 Correct 83 ms 6228 KB Output is correct
11 Correct 85 ms 6184 KB Output is correct
12 Correct 84 ms 6212 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 2956 KB Output is correct
2 Correct 435 ms 2856 KB Output is correct
3 Correct 884 ms 2992 KB Output is correct
4 Correct 518 ms 1864 KB Output is correct
5 Correct 753 ms 5460 KB Output is correct
6 Correct 977 ms 5380 KB Output is correct
7 Correct 729 ms 5712 KB Output is correct
8 Correct 1394 ms 5800 KB Output is correct
9 Correct 1274 ms 5760 KB Output is correct
10 Correct 1576 ms 5796 KB Output is correct
11 Correct 901 ms 5832 KB Output is correct
12 Correct 2361 ms 5904 KB Output is correct