oj.uz

답안 #31829

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
31829 2017-09-11T03:22:15 Z YoLo Sterilizing Spray (JOI15_sterilizing) C++14
0 / 100
 476 ms 5952 KB 
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define int long long
#define endl '\n'
#define pi acos(-1)
#define pque priority_queue
typedef pair < int, int > ii;
typedef vector < int > vi;
typedef vector < vi > vii;
int mod = 1000000007;
int lazy[202000], a[100009], n, m, K, f[202000];
void init(int k, int l, int r)
{
	lazy[k] = 1;
	if(l == r)
	{
		f[k] = a[l];
		return ;
	}
	int mid = (l + r) / 2;
	init(k * 2, l, mid);
	init(k * 2 + 1, mid + 1, r);
	f[k] = f[k * 2] + f[k * 2 + 1];
}
void dolazy(int k, int l, int r)
{
	f[k] = f[k] / lazy[k];
	if(l < r)
	{
		lazy[k * 2] = min(lazy[k * 2] * lazy[k], mod);
		lazy[k * 2 + 1] = min(lazy[k * 2 + 1] * lazy[k], mod);
	}
	lazy[k] = 1;
}
void upd(int k, int l, int r, int L, int R)
{
	dolazy(k, l, r);
	if(r < L || R < l || r < l)
		return ;
	if(L <= l && r <= R)
	{
		f[k] = f[k] / K;
		if(l < r)
		{
			lazy[k * 2] = min(lazy[k * 2] * K, mod);
			lazy[k * 2 + 1] = min(lazy[k * 2 + 1] * K, mod);
		}
		return ;
	}
	int mid = (l + r) / 2;
	upd(k * 2, l, mid, L, R);
	upd(k * 2 + 1, mid + 1, r, L, R);
	f[k] = f[k * 2] + f[k * 2 + 1];
}
void updd(int k, int l, int r, int pos, int val)
{
	dolazy(k, l, r);
	if(r < pos || l > pos)
		return;
	if(l == pos && r == pos)
	{
		f[k] = val;
		return;
	}
	int mid = (l + r) / 2;
	updd(k * 2, l, mid, pos, val);
	updd(k * 2 + 1, mid + 1, r, pos, val);
	f[k] = f[k * 2] + f[k * 2 + 1];
}
int getsum(int k, int l, int r, int L, int R)
{
	dolazy(k, l, r);
	if(r < L || R < l || r < l)
		return 0;
	if(L <= l && r <= R)
		return f[k];
	int mid = (l + r) / 2;
	return getsum(k * 2, l, mid, L, R) + getsum(k * 2 + 1, mid + 1, r, L, R);
}
signed main()
{
	cin >> n >> m >> K;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	init(1, 1, n);
	while(m --)
	{
		int t, l, r;
		cin >> t >> l >> r;
		if(t == 1)
			updd(1, 1, n, l, r);
		else if(t == 2)
			upd(1, 1, n, l, r);
		else
			cout << getsum(1, 1, n, l, r) << endl;
	}
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 306 ms 5952 KB Output is correct
2 Correct 476 ms 5952 KB Output is correct
3 Runtime error 33 ms 5952 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

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

Subtask #4
0 / 75.0

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