oj.uz

Submission #125123

# Submission time Handle Problem Language Result Execution time Memory
125123 2019-07-04T16:23:33 Z AuldLangSyne Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 307 ms 5980 KB 
#include <bits/stdc++.h>
#define ll long long
#define f(i, a, b) for(ll i = a; i <= b; ++i)
#define ff(i, a, b) for(ll i = a; i < b; ++i)
#define F(i, a, b) for(ll i = a; i >= b; --i)
#define FF(i, a, b) for(ll i = a; i > b; --i)
#define x first
#define y second
#define X real()
#define Y imag()
using namespace std;
typedef complex<ll> P;
typedef pair<ll, ll> ii;
typedef tuple<ll, ll, ll> iii;

const int N = 1e5+7;
int n, m, k, id, u, v;
ll a[N], node[4*N];

void build(int id, int l , int r){
	if(l == r){
		node[id] = a[r];
		return;
	}
	int mid = (l+r)/2;
	build(2*id, l, mid);
	build(2*id+1, mid+1, r);
	node[id] = node[2*id] + node[2*id+1];
}

void upd_point(int id, int l, int r, int pos, int val){
	if(pos < l || r < pos) return;
	if(l == r){
		node[id] = val;
		return;
	}
	int mid = (l+r)/2;
	upd_point(2*id, l, mid, pos, val);
	upd_point(2*id+1, mid+1, r, pos, val);
	node[id] = node[2*id] + node[2*id+1];
}

void upd_segment(int id, int l, int r, int u, int v){
	if(v < l || r < u || !node[id]) return;
	if(u <= l && r <= v){
		if(l == r){
			node[id] /= k;
			return;	
		}
	}
	int mid = (l+r)/2;
	upd_segment(2*id, l, mid, u, v);
	upd_segment(2*id+1, mid+1, r, u, v);
	node[id] = node[2*id]+node[2*id+1];
}

ll get_ans(int id, int l, int r, int u, int v){
	if(v < l || r < u) return 0;
	if(u <= l && r <= v) return node[id];
	int mid = (l+r)/2;
	return get_ans(2*id, l, mid, u, v) + get_ans(2*id+1, mid+1, r, u, v);
}

signed main(){
	scanf("%d %d %d", &n, &m, &k);
	f(i,1,n){
		scanf("%d", &a[i]);
	}
	build(1,1,n);
	while(m--){
		scanf("%d %d %d", &id, &u, &v);
		if(id == 1){
			upd_point(1,1,n,u,v);
		}else if(id == 2 && k > 1){
			upd_segment(1,1,n,u,v);
		}else if(id == 3){
			printf("%lld\n", get_ans(1,1,n,u,v));
		}
	}
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:67:20: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   scanf("%d", &a[i]);
               ~~~~~^
sterilizing.cpp:65:7: 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:67:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~
sterilizing.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &id, &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 6 ms 504 KB Output is correct
5 Correct 7 ms 504 KB Output is correct
6 Correct 6 ms 504 KB Output is correct
7 Correct 6 ms 504 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 504 KB Output is correct
11 Correct 6 ms 504 KB Output is correct
12 Correct 6 ms 508 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 3608 KB Output is correct
2 Correct 62 ms 3400 KB Output is correct
3 Correct 58 ms 4600 KB Output is correct
4 Correct 74 ms 4984 KB Output is correct
5 Correct 89 ms 4948 KB Output is correct
6 Correct 88 ms 4856 KB Output is correct
7 Correct 88 ms 4856 KB Output is correct
8 Correct 88 ms 4984 KB Output is correct
9 Correct 80 ms 4984 KB Output is correct
10 Correct 80 ms 4984 KB Output is correct
11 Correct 80 ms 5100 KB Output is correct
12 Correct 80 ms 5112 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1024 KB Output is correct
2 Correct 18 ms 2040 KB Output is correct
3 Correct 24 ms 2040 KB Output is correct
4 Correct 64 ms 2296 KB Output is correct
5 Correct 84 ms 4600 KB Output is correct
6 Correct 83 ms 4600 KB Output is correct
7 Correct 76 ms 4700 KB Output is correct
8 Correct 83 ms 4600 KB Output is correct
9 Correct 75 ms 4472 KB Output is correct
10 Correct 86 ms 4476 KB Output is correct
11 Correct 75 ms 4472 KB Output is correct
12 Correct 75 ms 4472 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 3556 KB Output is correct
2 Correct 121 ms 3684 KB Output is correct
3 Correct 136 ms 2936 KB Output is correct
4 Correct 143 ms 3012 KB Output is correct
5 Correct 174 ms 5884 KB Output is correct
6 Correct 200 ms 5936 KB Output is correct
7 Correct 169 ms 5980 KB Output is correct
8 Correct 242 ms 5948 KB Output is correct
9 Correct 204 ms 5724 KB Output is correct
10 Correct 233 ms 5820 KB Output is correct
11 Correct 175 ms 5752 KB Output is correct
12 Correct 307 ms 5920 KB Output is correct