oj.uz

답안 #342273

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
342273 2021-01-01T17:22:53 Z Nursik Sterilizing Spray (JOI15_sterilizing) C++14
15 / 100
 5000 ms 3692 KB 
#include <bits/stdc++.h>
          
#define fi first
#define se second
#define pp pop_back
#define ll long long
#define pb push_back
#define ld long double
#define debug cout << "OK\n";
#define all(x) x.begin(), x.end() 
#define mp make_pair 
using namespace std;        
 
const ll N = 1e6 + 200;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll pe = mod2; 
const ll pe2 = 570210983;
const ld eps = 1e-6; 
 
 
/*
Rucode: jaqVYNrpMj
JUDGE_ID: 295965SY
dl:160532
*/
void data() {
	#ifdef NURS
        freopen("main.in", "r", stdin);
        freopen("main.out", "w", stdout);
    #endif	
}
void speed_force() {
	ios_base::sync_with_stdio(0),
	cin.tie(0),cout.tie(0);
} 
                     
int n, q, k;
ll a[N];
ll f[N];
int type;
void upd(int pos, ll val)
{
	for (int i = pos; i <= n; i |= (i + 1))
	{
		f[i] += val;
	}
}
ll get(int pos)
{
	ll res = 0;
	for (int i = pos; i >= 1; i = (i & (i + 1)) - 1)
	{
		res += f[i];
	}
	return res;
}
int t[N * 4], m[N * 4];
void upd2(int pos, int val, int v = 1, int tl = 1, int tr = n)
{
	if (tl == tr)
	{
		t[v] = val;
		return;
	}
	int tm = (tl + tr) / 2;
	if (pos <= tm)
		upd2(pos, val, v * 2, tl, tm);
	else
		upd2(pos, val, v * 2 + 1, tm + 1, tr);
	t[v] = t[v * 2] + t[v * 2 + 1];
}
void push(int v, int tl, int tr)
{
	if (m[v])
	{
		t[v * 2] = t[v];
		t[v * 2 + 1] = t[v];
		m[v * 2] = m[v];
		m[v * 2 + 1] = m[v];
		m[v] = 0;
	}
}
int get3(int l, int r, int v = 1, int tl = 1, int tr = n)
{
	push(v, tl, tr);
	if (l <= tl && tr <= r)
		return t[v];
	if (l > tl || r < tl)
		return 0;
	int tm = (tl + tr) / 2;
	return get3(l, r, v * 2, tl, tm) + get3(l, r, v * 2 + 1, tm + 1, tr);
}
void get2(int l, int r, int v = 1, int tl = 1, int tr = n)
{
	push(v, tl, tr);
	if (l <= tl && tr <= r)
	{
		m[v] = 1;
		t[v] = 0;
		push(v, tl, tr);
		return;
	}
	if (l > tr || r < tl)
		return;
	int tm = (tl + tr) / 2;
	get2(l, r, v * 2, tl, tm);
	get2(l, r, v * 2 + 1, tm + 1, tr);
}
int main()
{
	data();     
	cin >> n >> q >> k;
	int check = 0;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		upd(i, a[i]);
		upd2(i, a[i]);
		check = (check | (a[i] > 1));
	}   
	//subtask 3
	if (check == 0)
	{
		for (int i = 1; i <= q; i++)
		{
			cin >> type;
			if (type == 1)
			{
				int pos, x;
				cin >> pos >> x;
				a[pos] = x;
				upd2(pos, x);
			}
			else if (type == 2)
			{
				int l, r;
				cin >> l >> r;
				get2(l, r);
			}
			else
			{
				int l, r;
				cin >> l >> r;
				cout << get3(l, r) << '\n';
			}
		}
		return 0;	
	}
	//subtask 2
	if (k == 1)
	{
		for (int i = 1; i <= q; i++)
		{
			cin >> type;
			if (type == 1)
			{
				int pos, x;
				cin >> pos >> x;
				upd(pos, -a[pos]);
				a[pos] = x;
				upd(pos, x);
			}
			else if (type == 2)
			{
				int l, r;
				cin >> l >> r;
			}
			else
			{
				int l, r;
				cin >> l >> r;
				cout << get(r) - get(l - 1) << '\n';
			}
		}
		return 0;
	}
	//subtask 1
	for (int i = 1; i <= q; i++)
	{
		cin >> type;
		if (type == 1)
		{
			int pos, x;
			cin >> pos >> x;
			upd(pos, -a[pos]);
			a[pos] = x;
			upd(pos, x);
		}
		else if (type == 2)
		{
			int l, r;
			cin >> l >> r;
			for (int j = l; j <= r; j++)
			{
				upd(j, -a[j]);
				upd(j, a[j] / k);
				a[j] /= k;
			}
		}
		else
		{
			int l, r;
			cin >> l >> r;
			cout << get(r) - get(l - 1) << '\n';
		}	
	}  
}
/*           
*/

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 364 KB Output is correct
2 Correct 3 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 10 ms 364 KB Output is correct
5 Correct 19 ms 492 KB Output is correct
6 Correct 17 ms 492 KB Output is correct
7 Correct 18 ms 492 KB Output is correct
8 Correct 16 ms 492 KB Output is correct
9 Correct 17 ms 492 KB Output is correct
10 Correct 17 ms 492 KB Output is correct
11 Correct 16 ms 492 KB Output is correct
12 Correct 18 ms 496 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 184 ms 2156 KB Output is correct
2 Correct 164 ms 1772 KB Output is correct
3 Correct 143 ms 2924 KB Output is correct
4 Correct 184 ms 3308 KB Output is correct
5 Correct 220 ms 3436 KB Output is correct
6 Correct 219 ms 3436 KB Output is correct
7 Correct 226 ms 3436 KB Output is correct
8 Correct 222 ms 3692 KB Output is correct
9 Correct 215 ms 3436 KB Output is correct
10 Correct 212 ms 3436 KB Output is correct
11 Correct 216 ms 3564 KB Output is correct
12 Correct 223 ms 3564 KB Output is correct

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 69 ms 748 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5046 ms 1900 KB Time limit exceeded
2 Halted 0 ms 0 KB -