oj.uz

Submission #159544

# Submission time Handle Problem Language Result Execution time Memory
159544 2019-10-23T05:25:47 Z Weak123456 Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 275 ms 7160 KB 
#include <bits/stdc++.h>
#define ii pair <int, int>
#define x first
#define y second
#define db(x) cerr << #x << " = " << x << endl;
#define _ << " _ " <<

using namespace std;

inline void read(int &x){register int c = getchar();x = 0; int neg = 0;for (;((c<48 || c>57) && c != '-') ;c = getchar());if(c=='-') {neg=1;c=getchar();}for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
inline void read(long long &x){register int c = getchar();x = 0; int neg = 0;for (;((c<48 || c>57) && c != '-') ;c = getchar());if(c=='-') {neg=1;c=getchar();}for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
inline void writeln(long long x){char buffor[21];register int i=0;int neg=0; if (x<0) {neg=1; x= -x;}do{buffor[i++]=(x%10)+'0';x/=10;} while(x);i--;if (neg) putchar('-');while(i>=0) putchar(buffor[i--]);putchar('\n');}
inline void write(long long x){char buffor[21];register int i=0;int neg=0; if (x<0) {neg=1; x= -x;}do{buffor[i++]=(x%10)+'0';x/=10;} while(x);i--;if (neg) putchar('-');while(i>=0) putchar(buffor[i--]);putchar(' ');}

const int N = 1e5 + 7;

int n, q, k;
int a[N];

struct segTree{
	long long tree[4 * N];
	int mx[4 * N];
	int leaf[N];

	inline void merge(int x){
		tree[x] = tree[x << 1] + tree[x << 1 | 1];
		mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
	}

	inline void Build(int x, int low, int high){
		if (low == high){
			tree[x] = a[low];
			mx[x] = a[low];
			leaf[low] = x;
		}
		else{
			int mid = low + high >> 1;
			Build(x << 1, low, mid);
			Build(x << 1 | 1, mid + 1, high);
			merge(x);
		}
	}

	inline void Update(int u, int val){
		int x = leaf[u];
		tree[x] = mx[x] = val;
		while (1){
			x >>= 1;
			if (!x) return;
			merge(x);
		}
	}

	inline void Divide(int x, int l, int h, int i, int j){
		if (l > j || h < i) return;
		if (l >= i && h <= j){
			if (mx[x] == 0) return;
			if (l == h){
				tree[x] /= k;
				mx[x] /= k;
				return;
			}	
		}
		int mid = l + h >> 1;
		Divide(2 * x, l, mid, i, j);
		Divide(2 * x + 1, mid + 1, h, i, j);
		merge(x);
	}

	inline long long Query(int x, int l, int h, int i, int j){
		if (l > j || h < i) return 0;
		if (l >= i && h <= j) return tree[x];
		int mid = l + h >> 1;
		return Query(x << 1, l, mid, i, j) + Query(x << 1 | 1, mid + 1, h, i, j);
	}
}IT;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	if(fopen("test.inp", "r")) freopen("test.inp", "r", stdin), freopen("test.out", "w", stdout);

	read(n); read(q); read(k);

	for (int i = 1; i <= n; i++)
		read(a[i]);

	IT.Build(1, 1, n);

	for (int i = 1; i <= q; i++){
		int type;
		read(type);

		if (type == 1){
			int id, val;
			read(id); read(val);
			IT.Update(id, val);
		}

		if (type == 2){
			int l, r;
			read(l); read(r);
			if (k != 1)
				IT.Divide(1, 1, n, l, r);
		}

		if (type == 3){
			int l, r;
			read(l); read(r);
			writeln(IT.Query(1, 1, n, l, r));
		}
	}
}

Compilation message

sterilizing.cpp: In member function 'void segTree::Build(int, int, int)':
sterilizing.cpp:37:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid = low + high >> 1;
              ~~~~^~~~~~
sterilizing.cpp: In member function 'void segTree::Divide(int, int, int, int, int)':
sterilizing.cpp:64:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l + h >> 1;
             ~~^~~
sterilizing.cpp: In member function 'long long int segTree::Query(int, int, int, int, int)':
sterilizing.cpp:73:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l + h >> 1;
             ~~^~~
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:82:60: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  if(fopen("test.inp", "r")) freopen("test.inp", "r", stdin), freopen("test.out", "w", stdout);
                             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:82:60: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 6 ms 504 KB Output is correct
5 Correct 6 ms 504 KB Output is correct
6 Correct 6 ms 504 KB Output is correct
7 Correct 6 ms 524 KB Output is correct
8 Correct 6 ms 504 KB Output is correct
9 Correct 7 ms 504 KB Output is correct
10 Correct 6 ms 528 KB Output is correct
11 Correct 6 ms 632 KB Output is correct
12 Correct 6 ms 504 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 2808 KB Output is correct
2 Correct 51 ms 4152 KB Output is correct
3 Correct 50 ms 6008 KB Output is correct
4 Correct 61 ms 6776 KB Output is correct
5 Correct 80 ms 7160 KB Output is correct
6 Correct 72 ms 7160 KB Output is correct
7 Correct 73 ms 7096 KB Output is correct
8 Correct 72 ms 7160 KB Output is correct
9 Correct 64 ms 7032 KB Output is correct
10 Correct 65 ms 7032 KB Output is correct
11 Correct 64 ms 7032 KB Output is correct
12 Correct 65 ms 7032 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 632 KB Output is correct
2 Correct 14 ms 2296 KB Output is correct
3 Correct 20 ms 2296 KB Output is correct
4 Correct 56 ms 1400 KB Output is correct
5 Correct 70 ms 4216 KB Output is correct
6 Correct 70 ms 4316 KB Output is correct
7 Correct 50 ms 4860 KB Output is correct
8 Correct 72 ms 5752 KB Output is correct
9 Correct 58 ms 5496 KB Output is correct
10 Correct 57 ms 5624 KB Output is correct
11 Correct 57 ms 5624 KB Output is correct
12 Correct 58 ms 5624 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 2540 KB Output is correct
2 Correct 115 ms 2640 KB Output is correct
3 Correct 129 ms 2424 KB Output is correct
4 Correct 136 ms 1648 KB Output is correct
5 Correct 181 ms 4600 KB Output is correct
6 Correct 187 ms 4472 KB Output is correct
7 Correct 159 ms 4536 KB Output is correct
8 Correct 225 ms 4548 KB Output is correct
9 Correct 181 ms 4600 KB Output is correct
10 Correct 207 ms 4616 KB Output is correct
11 Correct 155 ms 4600 KB Output is correct
12 Correct 275 ms 4576 KB Output is correct