oj.uz

Submission #47891

# Submission time Handle Problem Language Result Execution time Memory
47891 2018-05-08T11:59:24 Z Mamnoon_Siam Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 409 ms 70116 KB 
//#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
using namespace std;

#define debug(s) cout<< #s <<" = "<< s <<endl
#define all(v) (v).begin(), (v).end()
#define KeepUnique(v) (v).erase( unique(all(v)), v.end() )
#define MEMSET(a,val) memset(a, val, sizeof a)
#define PB push_back
#define endl '\n'

inline int myrand(int l, int r) {
	int ret = rand(); ret <<= 15; ret ^= rand();
	if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
	return ret;
}
template <typename F, typename S>
ostream& operator << (ostream& os, const pair< F, S>& p) {
    return os<<"(" <<p.first<<", "<<p.second<<")"; }

typedef pair<int, int> ii;
template<typename T> using min_pq =
	priority_queue<T, vector<T>, greater<T> >;

//int dx[] = {-1, +0, +1, +0};
//int dy[] = {+0, +1, +0, -1};

typedef long long ll;

const int maxn = 100010;

int n, q, k;
int a[maxn], mx[maxn * 4];
ll t[maxn * 4];

void replace(int u, int b, int e, int p, int v) {
	if(b > p or e < p) return;
	if(b == e) return void(t[u] = mx[u] = a[p] = v);
	int mid = b + e >> 1;
	replace(u << 1, b, mid, p, v);
	replace(u << 1 | 1, mid + 1, e, p, v);
	t[u] = t[u << 1] + t[u << 1 | 1];
	mx[u] = max(mx[u << 1], mx[u << 1 | 1]);
}

void update(int u, int b, int e, int i, int j) {
	if(b > j or e < i) return;
	if(mx[u] == 0) return;
	if(b == e) return void(t[u] = mx[u] = a[b] /= k);
	int mid = b + e >> 1;
	update(u << 1, b, mid, i, j);
	update(u << 1 | 1, mid + 1, e, i, j);
	t[u] = t[u << 1] + t[u << 1 | 1];
	mx[u] = max(mx[u << 1], mx[u << 1 | 1]);
}

void build(int u, int b, int e) {
	if(b == e) return void(t[u] = mx[u] = a[b]);
	int mid = b + e >> 1;
	build(u << 1, b, mid);
	build(u << 1 | 1, mid + 1, e);
	t[u] = t[u << 1] + t[u << 1 | 1];
	mx[u] = max(mx[u << 1], mx[u << 1 | 1]);
}

ll query(int u, int b, int e, int i, int j) {
	if(b > j or e < i) return 0;
	if(i <= b and e <= j) return t[u];
	int mid = b + e >> 1;
	return query(u << 1, b, mid, i, j) + query(u << 1 | 1, mid + 1, e, i, j);
}

int32_t main () {
	//freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
	cin>>n>>q>>k;
	for(int i=1; i<=n; i++) {
		cin>>a[i];
	}
	build(1, 1, n);
	while(q--) {
		int s, t, u;
		cin>>s>>t>>u;
		if(s == 1) {
			replace(1, 1, n, t, u);
		} else if(s == 2) {
			if(k != 1) {
				update(1, 1, n, t, u);
			}
		} else {
			cout<<query(1, 1, n, t, u)<<endl;
		}
	}
	return 0;
}

Compilation message

sterilizing.cpp: In function 'int myrand(int, int)':
sterilizing.cpp:16:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
  ^~
sterilizing.cpp:16:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
                          ^~~
sterilizing.cpp: In function 'void replace(int, int, int, int, int)':
sterilizing.cpp:41:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = b + e >> 1;
            ~~^~~
sterilizing.cpp: In function 'void update(int, int, int, int, int)':
sterilizing.cpp:52:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = b + e >> 1;
            ~~^~~
sterilizing.cpp: In function 'void build(int, int, int)':
sterilizing.cpp:61:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = b + e >> 1;
            ~~^~~
sterilizing.cpp: In function 'll query(int, int, int, int, int)':
sterilizing.cpp:71:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = b + e >> 1;
            ~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 392 KB Output is correct
2 Correct 4 ms 604 KB Output is correct
3 Correct 3 ms 752 KB Output is correct
4 Correct 10 ms 752 KB Output is correct
5 Correct 10 ms 836 KB Output is correct
6 Correct 13 ms 956 KB Output is correct
7 Correct 10 ms 1024 KB Output is correct
8 Correct 10 ms 1220 KB Output is correct
9 Correct 10 ms 1328 KB Output is correct
10 Correct 10 ms 1384 KB Output is correct
11 Correct 15 ms 1392 KB Output is correct
12 Correct 15 ms 1460 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 5628 KB Output is correct
2 Correct 168 ms 7092 KB Output is correct
3 Correct 155 ms 10388 KB Output is correct
4 Correct 196 ms 12664 KB Output is correct
5 Correct 240 ms 15268 KB Output is correct
6 Correct 229 ms 17652 KB Output is correct
7 Correct 241 ms 20184 KB Output is correct
8 Correct 231 ms 22588 KB Output is correct
9 Correct 225 ms 24964 KB Output is correct
10 Correct 217 ms 27288 KB Output is correct
11 Correct 220 ms 29616 KB Output is correct
12 Correct 227 ms 31908 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 31908 KB Output is correct
2 Correct 38 ms 31908 KB Output is correct
3 Correct 67 ms 31908 KB Output is correct
4 Correct 161 ms 31908 KB Output is correct
5 Correct 198 ms 35316 KB Output is correct
6 Correct 202 ms 36572 KB Output is correct
7 Correct 193 ms 38284 KB Output is correct
8 Correct 193 ms 39452 KB Output is correct
9 Correct 233 ms 40748 KB Output is correct
10 Correct 193 ms 42020 KB Output is correct
11 Correct 209 ms 43712 KB Output is correct
12 Correct 178 ms 44708 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 44708 KB Output is correct
2 Correct 212 ms 46364 KB Output is correct
3 Correct 190 ms 47400 KB Output is correct
4 Correct 247 ms 48368 KB Output is correct
5 Correct 301 ms 53472 KB Output is correct
6 Correct 319 ms 55792 KB Output is correct
7 Correct 292 ms 58252 KB Output is correct
8 Correct 355 ms 60772 KB Output is correct
9 Correct 321 ms 63148 KB Output is correct
10 Correct 345 ms 65452 KB Output is correct
11 Correct 295 ms 67716 KB Output is correct
12 Correct 409 ms 70116 KB Output is correct