oj.uz

Submission #159543

# Submission time Handle Problem Language Result Execution time Memory
159543 2019-10-23T05:24:07 Z Weak123456 Sterilizing Spray (JOI15_sterilizing) C++14
80 / 100
 5000 ms 7032 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);
			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 4 ms 376 KB Output is correct
2 Correct 5 ms 376 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 632 KB Output is correct
6 Correct 6 ms 632 KB Output is correct
7 Correct 6 ms 632 KB Output is correct
8 Correct 6 ms 636 KB Output is correct
9 Correct 7 ms 632 KB Output is correct
10 Correct 6 ms 632 KB Output is correct
11 Correct 6 ms 632 KB Output is correct
12 Correct 6 ms 632 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5079 ms 2760 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 636 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 72 ms 4344 KB Output is correct
6 Correct 71 ms 4216 KB Output is correct
7 Execution timed out 5092 ms 4696 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 2424 KB Output is correct
2 Correct 109 ms 4216 KB Output is correct
3 Correct 131 ms 3552 KB Output is correct
4 Correct 134 ms 3320 KB Output is correct
5 Correct 169 ms 6904 KB Output is correct
6 Correct 189 ms 7032 KB Output is correct
7 Correct 162 ms 6904 KB Output is correct
8 Correct 226 ms 6960 KB Output is correct
9 Correct 183 ms 6852 KB Output is correct
10 Correct 207 ms 6904 KB Output is correct
11 Correct 158 ms 6856 KB Output is correct
12 Correct 275 ms 6840 KB Output is correct