제출 #159544

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
159544		Weak123456	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	275 ms	7160 KiB

sterilizing

#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));
		}
	}
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75