oj.uz

Submission #527853

# Submission time Handle Problem Language Result Execution time Memory
527853 2022-02-18T13:59:23 Z AriaH Sterilizing Spray (JOI15_sterilizing) C++17
80 / 100
 5000 ms 8204 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)
		{
			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 3 ms 332 KB Output is correct
2 Correct 22 ms 400 KB Output is correct
3 Correct 7 ms 332 KB Output is correct
4 Correct 22 ms 468 KB Output is correct
5 Correct 23 ms 460 KB Output is correct
6 Correct 15 ms 556 KB Output is correct
7 Correct 20 ms 592 KB Output is correct
8 Correct 22 ms 636 KB Output is correct
9 Correct 27 ms 588 KB Output is correct
10 Correct 19 ms 576 KB Output is correct
11 Correct 18 ms 568 KB Output is correct
12 Correct 20 ms 464 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5012 ms 3864 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1104 KB Output is correct
2 Correct 21 ms 2868 KB Output is correct
3 Correct 30 ms 2972 KB Output is correct
4 Correct 58 ms 2752 KB Output is correct
5 Correct 103 ms 6500 KB Output is correct
6 Correct 93 ms 6340 KB Output is correct
7 Execution timed out 5052 ms 5684 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 402 ms 4500 KB Output is correct
2 Correct 398 ms 4600 KB Output is correct
3 Correct 917 ms 4192 KB Output is correct
4 Correct 506 ms 3728 KB Output is correct
5 Correct 748 ms 7792 KB Output is correct
6 Correct 1053 ms 7860 KB Output is correct
7 Correct 706 ms 8204 KB Output is correct
8 Correct 1408 ms 7964 KB Output is correct
9 Correct 1247 ms 7656 KB Output is correct
10 Correct 1578 ms 8108 KB Output is correct
11 Correct 914 ms 7660 KB Output is correct
12 Correct 2481 ms 7940 KB Output is correct