oj.uz

Submission #106142

# Submission time Handle Problem Language Result Execution time Memory
106142 2019-04-16T18:32:19 Z cki86201 Sterilizing Spray (JOI15_sterilizing) C++11
100 / 100
 325 ms 6812 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_set>
#include <bitset>
#include <time.h>
#include <limits.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define Fi first
#define Se second
#define pb push_back
#define szz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
typedef tuple<int, int, int> t3;

int N, K, Q;
int A[100010];

ll T[1<<18];
int H[1<<18];

void init(int rt, int l, int r) {
	if(l == r) T[rt] = A[l];
	else {
		int m = (l + r) >> 1;
		init(rt*2, l, m);
		init(rt*2+1, m+1, r);
		T[rt] = T[rt*2] + T[rt*2+1];
		H[rt] = H[rt*2] & H[rt*2+1];
	}
}

void update_v(int rt, int l, int r, int x, int v) {
	if(l == r) {
		T[rt] = v;
		H[rt] = (v == 0);
		return;
	}
	int m = (l + r) >> 1;
	if(x <= m) update_v(rt*2, l, m, x, v);
	else update_v(rt*2+1, m+1, r, x, v);
	T[rt] = T[rt*2] + T[rt*2+1];
	H[rt] = H[rt*2] & H[rt*2+1];
}

void update_s(int rt, int l, int r, int s, int e) {
	if(H[rt]) return;
	if(l == r) {
		T[rt] /= K;
		H[rt] = (T[rt] == 0);
		return;
	}
	int m = (l + r) >> 1;
	if(s <= m) update_s(rt*2, l, m, s, e);
	if(m < e) update_s(rt*2+1, m+1, r, s, e);
	T[rt] = T[rt*2] + T[rt*2+1];
	H[rt] = H[rt*2] & H[rt*2+1];
}

ll get_sum(int rt, int l, int r, int s, int e) {
	if(s <= l && r <= e) return T[rt];
	int m = (l + r) >> 1;
	ll res = 0;
	if(s <= m) res += get_sum(rt*2, l, m, s, e);
	if(m < e) res += get_sum(rt*2+1, m+1, r, s, e);
	return res;
}

int main() {
	scanf("%d%d%d", &N, &Q, &K);
	for(int i=1;i<=N;i++) scanf("%d", A + i);
	init(1, 1, N);
	for(int i=1;i<=Q;i++) {
		int cmd; scanf("%d", &cmd);
		if(cmd == 1) {
			int x, y; scanf("%d%d", &x, &y);
			update_v(1, 1, N, x, y);
		}
		else if(cmd == 2) {
			int l, r; scanf("%d%d", &l, &r);
			if(K > 1) update_s(1, 1, N, l, r);
		}
		else {
			int l, r; scanf("%d%d", &l, &r);
			printf("%lld\n", get_sum(1, 1, N, l, r));
		}
	}
	return 0;
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:86:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &Q, &K);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:87:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=N;i++) scanf("%d", A + i);
                        ~~~~~^~~~~~~~~~~~~
sterilizing.cpp:90:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int cmd; scanf("%d", &cmd);
            ~~~~~^~~~~~~~~~~~
sterilizing.cpp:92:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int x, y; scanf("%d%d", &x, &y);
              ~~~~~^~~~~~~~~~~~~~~~
sterilizing.cpp:96:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int l, r; scanf("%d%d", &l, &r);
              ~~~~~^~~~~~~~~~~~~~~~
sterilizing.cpp:100:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int l, r; scanf("%d%d", &l, &r);
              ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 7 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 560 KB Output is correct
8 Correct 9 ms 512 KB Output is correct
9 Correct 11 ms 512 KB Output is correct
10 Correct 7 ms 512 KB Output is correct
11 Correct 6 ms 384 KB Output is correct
12 Correct 6 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 2912 KB Output is correct
2 Correct 59 ms 4088 KB Output is correct
3 Correct 59 ms 5624 KB Output is correct
4 Correct 76 ms 6264 KB Output is correct
5 Correct 107 ms 6636 KB Output is correct
6 Correct 109 ms 6808 KB Output is correct
7 Correct 116 ms 6812 KB Output is correct
8 Correct 92 ms 6648 KB Output is correct
9 Correct 84 ms 6520 KB Output is correct
10 Correct 95 ms 6640 KB Output is correct
11 Correct 81 ms 6628 KB Output is correct
12 Correct 85 ms 6608 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 512 KB Output is correct
2 Correct 30 ms 2176 KB Output is correct
3 Correct 25 ms 2048 KB Output is correct
4 Correct 70 ms 1408 KB Output is correct
5 Correct 86 ms 3984 KB Output is correct
6 Correct 94 ms 3960 KB Output is correct
7 Correct 72 ms 4600 KB Output is correct
8 Correct 99 ms 5376 KB Output is correct
9 Correct 72 ms 5240 KB Output is correct
10 Correct 93 ms 5228 KB Output is correct
11 Correct 83 ms 5124 KB Output is correct
12 Correct 72 ms 5156 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 2292 KB Output is correct
2 Correct 114 ms 2268 KB Output is correct
3 Correct 140 ms 2296 KB Output is correct
4 Correct 144 ms 1528 KB Output is correct
5 Correct 171 ms 4088 KB Output is correct
6 Correct 205 ms 4116 KB Output is correct
7 Correct 171 ms 4108 KB Output is correct
8 Correct 325 ms 4216 KB Output is correct
9 Correct 274 ms 4216 KB Output is correct
10 Correct 208 ms 4196 KB Output is correct
11 Correct 163 ms 4216 KB Output is correct
12 Correct 292 ms 4180 KB Output is correct