oj.uz

답안 #385461

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
385461 2021-04-04T11:23:16 Z Return_0 Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 768 ms 69612 KB 
// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma comment(linker, "/stack:200000000")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

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

#ifdef SINA
#define dbg(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1> void __f(const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << std::endl; }
template <typename Arg1, typename... Args> void __f (const char* names, Arg1&& arg1, Args&&... args) {
	const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...); }
#define dbg2(x, j, n) cout<< #x << " : "; output((j), (n), x, 1); cout.flush();
#else
#define dbg(...) 0
#define dbg2(x, j, n) 0
#endif
#define SZ(x) ((ll)((x).size()))
#define File(s, t) freopen(s ".txt", "r", stdin); freopen(t ".txt", "w", stdout);
#define input(j, n, a) for (int _i = (j); _i < (n)+(j); _i++) cin>> a[_i];
#define output(j, n, a, t) for (int _i = (j); _i < (n)+(j); _i++) cout<< a[_i] << (((t) && _i != (n)+(j)-1)? ' ' : '\n');
#define kill(x) return cout<< (x) << endl, 0
#define cl const ll
#define fr first
#define sc second
#define lc (v << 1)
#define rc (lc | 1)
#define mid ((l + r) >> 1)
#define All(x) (x).begin(), (x).end()

cl inf = sizeof(ll) == 4 ? (1e9 + 10) : (3e18), mod = 1e9 + 7, MOD = 998244353;

template <class A,class B> ostream& operator << (ostream& out,const pair<A,B>&a){return out<<'('<<a.first<<", "<<a.second<<')';}
template <class A> ostream& operator << (ostream& out, const vector<A> &a) {
	out<< '['; for (int i = -1; ++i < int(a.size());) out<< a[i] << (i + 1 < int(a.size()) ? ", " : ""); return out<<']'; }
template <class T, typename _t = less <T> > using Tree = tree <T, null_type, _t, rb_tree_tag, tree_order_statistics_node_update>;

cl N = 1e5 + 7;

ll a [N], n, k, tf = 1, q, len = 1;

struct node {
	vector <ll> num;
	node () {}
	node (ll x) {
		num.resize(len);
		for (ll i = 0; x; i++, x /= k) num[i] = x % k;
	}
	friend node operator + (const node &x, const node &y) {
		node ret; ret.num.resize(len);
		for (ll i = 0; i < len; i++) ret.num[i] = x.num[i] + y.num[i];
		return ret;
	}
	ll conv () {
		ll ret = 0;
		for (ll i = len; i--;) ret = ret * k + num[i];
		return ret;
	}
};

struct segtree {
	node n;
	ll l, r, lz;
	segtree *lt, *rt;
	inline segtree (cl &L = 1, cl &R = N - 2) : l(L), r(R), lz(0) {}

	void build () {
		if (l == r) {
			n = node(a[l]);
			return;
		}
		lt = new segtree (l, mid);
		rt = new segtree (mid + 1, r);
		lt->build();
		rt->build();
		n = lt->n + rt->n;
	}

	inline void push (cl &x) {
		for (ll i = 0; i < len - x; i++) n.num[i] = n.num[i + x];
		for (ll i = max(len - x, 0LL); i < len; i++) n.num[i] = 0;
		lz += x;
	}
	inline void shift () { if (lz) { lt->push(lz); rt->push(lz); lz = 0; } }

	void modify (cl &pos, cl &x) {
		if (l == r) {
			n = node(x);
			return;
		}
		shift();
		if (pos <= lt->r) lt->modify(pos, x);
		else rt->modify(pos, x);
		n = lt->n + rt->n;
	}

	void upd (cl &ql, cl &qr) {
		if (r < ql || qr < l)   return;
		if (ql <= l && r <= qr) {
			push(1);
			return;
		}
		shift();
		lt->upd(ql, qr);
		rt->upd(ql, qr);
		n = lt->n + rt->n;
	}

	ll ask (cl &ql, cl &qr) {
		if (r < ql || qr < l)   return 0;
		if (ql <= l && r <= qr) return n.conv();
		shift();
		return lt->ask(ql, qr) + rt->ask(ql, qr);
	}
} seg;

int main ()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin>> n >> q >> k;
	for (ll i = 1; i <= n; i++) cin>> a[i];
	if (k == 1) k = 10, tf = 0;

	for (ll i = 1; i < mod; len++, i *= k);
	seg.r = n; seg.build();

	for (ll t, l, r; q--;) {
		cin>> t >> l >> r;
		if (t == 1) seg.modify(l, r);
		else if (t == 3) cout<< seg.ask(l, r) << '\n';
		else if (tf) seg.upd(l, r);
	}

	cerr<< "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";

	return 0;
}
/*

*/

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 364 KB Output is correct
2 Correct 3 ms 620 KB Output is correct
3 Correct 2 ms 1004 KB Output is correct
4 Correct 10 ms 1388 KB Output is correct
5 Correct 9 ms 1792 KB Output is correct
6 Correct 7 ms 1516 KB Output is correct
7 Correct 8 ms 1644 KB Output is correct
8 Correct 8 ms 1644 KB Output is correct
9 Correct 10 ms 2028 KB Output is correct
10 Correct 8 ms 1644 KB Output is correct
11 Correct 8 ms 1644 KB Output is correct
12 Correct 8 ms 1644 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 175 ms 18668 KB Output is correct
2 Correct 145 ms 13332 KB Output is correct
3 Correct 152 ms 28780 KB Output is correct
4 Correct 192 ms 36332 KB Output is correct
5 Correct 239 ms 36972 KB Output is correct
6 Correct 247 ms 37100 KB Output is correct
7 Correct 232 ms 36972 KB Output is correct
8 Correct 232 ms 36972 KB Output is correct
9 Correct 198 ms 36972 KB Output is correct
10 Correct 235 ms 37100 KB Output is correct
11 Correct 204 ms 36844 KB Output is correct
12 Correct 209 ms 36716 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 80 ms 3564 KB Output is correct
2 Correct 87 ms 23404 KB Output is correct
3 Correct 95 ms 16620 KB Output is correct
4 Correct 283 ms 10476 KB Output is correct
5 Correct 533 ms 46444 KB Output is correct
6 Correct 768 ms 68544 KB Output is correct
7 Correct 212 ms 37356 KB Output is correct
8 Correct 460 ms 40428 KB Output is correct
9 Correct 285 ms 37100 KB Output is correct
10 Correct 309 ms 40044 KB Output is correct
11 Correct 287 ms 37100 KB Output is correct
12 Correct 342 ms 46444 KB Output is correct

Subtask #4
75.0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 270 ms 19692 KB Output is correct
2 Correct 306 ms 20588 KB Output is correct
3 Correct 354 ms 31596 KB Output is correct
4 Correct 387 ms 16620 KB Output is correct
5 Correct 460 ms 38380 KB Output is correct
6 Correct 508 ms 44772 KB Output is correct
7 Correct 469 ms 38252 KB Output is correct
8 Correct 652 ms 54124 KB Output is correct
9 Correct 388 ms 47724 KB Output is correct
10 Correct 433 ms 54124 KB Output is correct
11 Correct 334 ms 41580 KB Output is correct
12 Correct 620 ms 69612 KB Output is correct