oj.uz

답안 #159541

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
159541 2019-10-23T05:22:55 Z Weak123456 Sterilizing Spray (JOI15_sterilizing) C++14
0 / 100
 5000 ms 4604 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{
	int 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
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5008 ms 4160 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 1016 KB Output is correct
2 Correct 14 ms 2040 KB Output is correct
3 Correct 19 ms 2168 KB Output is correct
4 Correct 55 ms 2380 KB Output is correct
5 Correct 68 ms 4600 KB Output is correct
6 Correct 68 ms 4604 KB Output is correct
7 Execution timed out 5010 ms 4396 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 93 ms 3448 KB Output isn't correct
2 Halted 0 ms 0 KB -