oj.uz

Submission #34586

# Submission time Handle Problem Language Result Execution time Memory
34586 2017-11-14T01:28:14 Z sinhriv Sterilizing Spray (JOI15_sterilizing) C++14
10 / 100
 389 ms 46576 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n, K, m;
long long pw[N];

struct SegmentTree{
	int lazy[N << 3];
	int modun[N << 3][11];
	long long sum[N << 3];

	#define mid ((l + r) >> 1)

	void push(int x){
		if(lazy[x] != 0){
			int tot = 0;
			for(int i = 0; i < K; ++i){
				sum[x] -= modun[x][i] * i;
				tot += modun[x][i];
			}

			modun[x][0] = tot;
			sum[x] /= pw[lazy[x]];
			lazy[x + x] += lazy[x];
			lazy[x + x + 1] += lazy[x];
		}
		lazy[x] = 0;
	}

	void reCalc(int x){
		sum[x] = sum[x + x] + sum[x + x + 1];
		for(int i = 0; i < K; ++i){
			modun[x][i] = modun[x + x][i] + modun[x + x + 1][i];
		}
	}

	void update(int x, int l, int r, int u, int v){
		push(x);
		if(l > v || r < u) return;	
		if(l >= u && r <= v){
			++lazy[x];
			push(x);
			return;
		}
		update(x + x, l, mid, u, v);
		update(x + x + 1, mid + 1, r, u, v);
		reCalc(x);
	}

	void modify(int x, int l, int r, int u, int val){
		push(x);
		if(l > u || r < u) return;
		if(l == r){
			reCalc(x);
			sum[x] = val;
			++modun[x][val % K];
			return;
		}
		modify(x + x, l, mid, u, val);
		modify(x + x + 1, mid + 1, r, u, val);
		reCalc(x);
	}

	long long query(int x, int l, int r, int u, int v){
		push(x);
		if(l >= u && r <= v) return sum[x];
		if(l > v || r < u) return 0;
		long long ret = query(x + x, l, mid, u, v) + query(x + x + 1, mid + 1, r, u, v);
		reCalc(x);
		return ret;
	}
}Smt;

int main(){
	if(fopen("1.inp", "r")){
		freopen("1.inp", "r", stdin);
	}

	scanf("%d%d%d", &n, &m, &K);


	pw[0] = 1;
	for(int i = 1; i <= m; ++i){
		if(1e18 / pw[i - 1] < K) pw[i] = 1e18;
		else pw[i] = pw[i - 1] * K;
	}


	for(int i = 1; i <= n; ++i){
		int x;
		scanf("%d", &x);
		Smt.modify(1, 1, n, i, x);
	}


	while(m--){
		int t, u, v;
		scanf("%d%d%d", &t, &u, &v);


		if(t == 1){
			Smt.modify(1, 1, n, u, v);
		}
		if(t == 2){
			Smt.update(1, 1, n, u, v);
		}


		if(t == 3){
			printf("%lld\n", Smt.query(1, 1, n, u, v));
		}
	}

	return 0;
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:79:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen("1.inp", "r", stdin);
                               ^
sterilizing.cpp:82:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &m, &K);
                             ^
sterilizing.cpp:94:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
                  ^
sterilizing.cpp:101:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &t, &u, &v);
                              ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 46576 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 46576 KB Output is correct
2 Correct 209 ms 46576 KB Output is correct
3 Correct 209 ms 46576 KB Output is correct
4 Correct 296 ms 46576 KB Output is correct
5 Correct 389 ms 46576 KB Output is correct
6 Correct 356 ms 46576 KB Output is correct
7 Correct 363 ms 46576 KB Output is correct
8 Correct 349 ms 46576 KB Output is correct
9 Correct 236 ms 46576 KB Output is correct
10 Correct 256 ms 46576 KB Output is correct
11 Correct 246 ms 46576 KB Output is correct
12 Correct 266 ms 46576 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 46576 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 229 ms 46576 KB Output isn't correct
2 Halted 0 ms 0 KB -