oj.uz

Submission #395706

# Submission time Handle Problem Language Result Execution time Memory
395706 2021-04-28T19:09:49 Z arwaeystoamneg Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 729 ms 101964 KB 
// EXPLOSION!
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include<chrono>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpll;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define pb push_back
#define mp make_pair
#define rsz resize
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define cont continue
#define endl '\n'
//#define ednl '\n'
#define test int testc;cin>>testc;while(testc--)
#define pr(a, b) trav(x,a)cerr << x << b; cerr << endl;
#define message cout << "Hello World" << endl;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!!
const ll linf = 4000000000000000000LL;
const ll inf = 1000000007;//998244353    

void pv(vi a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vll a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vector<vi>a) {
	F0R(i, sz(a)) { cout << i << endl; pv(a[i]); cout << endl; }
}void pv(vector<vll>a) { F0R(i, sz(a)) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; }
void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef arwaeystoamneg
	if (sz(s))
	{
		freopen((s + ".in").c_str(), "r", stdin);
		if (s != "test1")
			freopen((s + ".out").c_str(), "w", stdout);
	}
#endif
}
template<class T, int MAX> struct st
{
	T tree[2 * MAX];
	void init(T* a)
	{
		init(0, 0, MAX - 1, a);
	}
	void init(int i, int tl, int tr, T* a)
	{
		if (tl == tr)
		{
			tree[i] = a[tl];
		}
		else
		{
			int m = (tl + tr) / 2;
			init(2 * i + 1, tl, m, a);
			init(2 * i + 2, m + 1, tr, a);
			tree[i] = tree[2 * i + 1] + tree[2 * i + 2];
		}
	}
	T query(int l, int r)
	{
		return query(0, 0, MAX - 1, l, r);
	}
	T query(int i, int tl, int tr, int l, int r)
	{
		if (tl != tr)
		{
			tree[2 * i + 1].lazy += tree[i].lazy;
			tree[2 * i + 2].lazy += tree[i].lazy;
		}
		tree[i].push();
		if (r<tl || l>tr)return T(0);
		if (l <= tl && r >= tr)return tree[i];
		int m = (tl + tr) / 2;
		return query(2 * i + 1, tl, m, l, r) + query(2 * i + 2, m + 1, tr, l, r);
	}
	void update(int x, T y)
	{
		update(0, 0, MAX - 1, x, y);
	}
	void update(int i, int tl, int tr, int x, T y)
	{
		if (tl != tr)
		{
			tree[2 * i + 1].lazy += tree[i].lazy;
			tree[2 * i + 2].lazy += tree[i].lazy;
		}
		tree[i].push();
		if (x > tr || x < tl)return;
		if (tl == tr)tree[i] = y;
		else
		{
			int m = (tl + tr) / 2;
			update(2 * i + 1, tl, m, x, y);
			update(2 * i + 2, m + 1, tr, x, y);
			tree[i] = tree[2 * i + 1] + tree[2 * i + 2];
		}
	}
	void spray(int l, int r)
	{
		spray(0, 0, MAX - 1, l, r);
	}
	void spray(int i, int tl, int tr, int l, int r)
	{
		if (tl != tr)
		{
			tree[2 * i + 1].lazy += tree[i].lazy;
			tree[2 * i + 2].lazy += tree[i].lazy;
		}
		tree[i].push();
		if (r<tl || l>tr)return;
		if (tl >= l && tr <= r)
		{
			tree[i].lazy++;
			if (tl != tr)
			{
				tree[2 * i + 1].lazy += tree[i].lazy;
				tree[2 * i + 2].lazy += tree[i].lazy;
			}
			tree[i].push();
		}
		else
		{
			int m = (tl + tr) / 2;
			spray(2 * i + 1, tl, m, l, r);
			spray(2 * i + 2, m + 1, tr, l, r);
			tree[i] = tree[2 * i + 1] + tree[2 * i + 2];
		}
	}
};
struct inte
{
	ll x, lazy;
	inte()
	{
		lazy = x = 0;
	}
	inte(ll t)
	{
		lazy = 0;
		x = t;
	}
	void push()
	{
		assert(!lazy);
	}
	inte operator+(const inte& a)const
	{
		return inte(a.x + x);
	}
};
const int MAX = 1 << 17, SZ = 31;
int n, k, q, a[MAX];
struct T
{
	int lazy;
	ll a[SZ];
	T()
	{
		lazy = 0;
		F0R(i, SZ)a[i] = 0;
	}
	T(int x)
	{
		lazy = 0;
		F0R(i, SZ)a[i] = 0;
		int i = 0;
		while (x)
		{
			a[i] += x;
			x /= k;
			i++;
		}
	}
	void push()
	{
		if (lazy)
		{
			F0R(i, SZ - lazy)a[i] = a[i + lazy];
			FOR(i, max(0, SZ - lazy), SZ)a[i] = 0;
			lazy = 0;
		}
	}
	T operator+(const T& x)const
	{
		assert(!lazy && !x.lazy);
		T res(0);
		F0R(i, SZ)res.a[i] = x.a[i] + a[i];
		return res;
	}
};
int main() 
{
	setIO("test1");
	cin >> n >> q >> k;
	F0R(i, n)cin >> a[i];
	if (k == 1)
	{
		inte b[MAX];
		st<inte, MAX>t;
		F0R(i, n)b[i] = inte(a[i]);
		FOR(i, n, MAX)b[i] = 0;
		t.init(b);
		while (q--)
		{
			int x, y, z;
			cin >> x >> y >> z;
			x--, y--, z--;
			if (x == 0)
			{
				t.update(y, z + 1);
			}
			else if(x == 1)
			{

			}
			else
			{
				cout << t.query(y, z).x << endl;
			}
		}
		return 0;
	}
	T b[MAX];
	st<T, MAX>t;
	F0R(i, n)b[i] = T(a[i]);
	FOR(i, n, MAX)b[i] = T(0);
	t.init(b);
	while (q--)
	{
		int x, y, z;
		cin >> x >> y >> z;
		x--, y--, z--;
		if (x == 0)
		{
			t.update(y, T(z + 1));
		}
		else if (x == 1)
		{
			t.spray(y, z);
		}
		else
		{
			cout << t.query(y, z).a[0] << endl;
		}
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 98756 KB Output is correct
2 Correct 6 ms 6476 KB Output is correct
3 Correct 67 ms 98832 KB Output is correct
4 Correct 77 ms 98844 KB Output is correct
5 Correct 88 ms 98812 KB Output is correct
6 Correct 84 ms 98884 KB Output is correct
7 Correct 78 ms 98868 KB Output is correct
8 Correct 80 ms 98884 KB Output is correct
9 Correct 79 ms 98808 KB Output is correct
10 Correct 80 ms 98868 KB Output is correct
11 Correct 86 ms 98884 KB Output is correct
12 Correct 80 ms 98896 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 7104 KB Output is correct
2 Correct 61 ms 6980 KB Output is correct
3 Correct 51 ms 6980 KB Output is correct
4 Correct 71 ms 7364 KB Output is correct
5 Correct 77 ms 7244 KB Output is correct
6 Correct 80 ms 7236 KB Output is correct
7 Correct 95 ms 7264 KB Output is correct
8 Correct 80 ms 7236 KB Output is correct
9 Correct 82 ms 7500 KB Output is correct
10 Correct 78 ms 7356 KB Output is correct
11 Correct 90 ms 7364 KB Output is correct
12 Correct 71 ms 7364 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 98872 KB Output is correct
2 Correct 150 ms 99276 KB Output is correct
3 Correct 200 ms 99348 KB Output is correct
4 Correct 541 ms 100060 KB Output is correct
5 Correct 720 ms 100688 KB Output is correct
6 Correct 720 ms 100676 KB Output is correct
7 Correct 72 ms 8388 KB Output is correct
8 Correct 706 ms 100676 KB Output is correct
9 Correct 514 ms 100488 KB Output is correct
10 Correct 535 ms 100592 KB Output is correct
11 Correct 514 ms 100516 KB Output is correct
12 Correct 521 ms 100544 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 461 ms 99140 KB Output is correct
2 Correct 535 ms 100940 KB Output is correct
3 Correct 349 ms 100276 KB Output is correct
4 Correct 621 ms 101096 KB Output is correct
5 Correct 697 ms 101956 KB Output is correct
6 Correct 713 ms 101924 KB Output is correct
7 Correct 711 ms 101824 KB Output is correct
8 Correct 729 ms 101964 KB Output is correct
9 Correct 546 ms 101732 KB Output is correct
10 Correct 529 ms 101776 KB Output is correct
11 Correct 534 ms 101792 KB Output is correct
12 Correct 562 ms 101948 KB Output is correct