oj.uz

Submission #125120

# Submission time Handle Problem Language Result Execution time Memory
125120 2019-07-04T16:19:39 Z AuldLangSyne Sterilizing Spray (JOI15_sterilizing) C++14
15 / 100
 5000 ms 6136 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) 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("%lld", &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: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("%lld", &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 11 ms 376 KB Output is correct
5 Correct 20 ms 504 KB Output is correct
6 Correct 21 ms 504 KB Output is correct
7 Correct 20 ms 504 KB Output is correct
8 Correct 20 ms 504 KB Output is correct
9 Correct 21 ms 504 KB Output is correct
10 Correct 21 ms 504 KB Output is correct
11 Correct 20 ms 504 KB Output is correct
12 Correct 21 ms 504 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 4056 KB Output is correct
2 Correct 62 ms 3612 KB Output is correct
3 Correct 59 ms 4984 KB Output is correct
4 Correct 75 ms 5612 KB Output is correct
5 Correct 90 ms 6060 KB Output is correct
6 Correct 90 ms 6136 KB Output is correct
7 Correct 93 ms 6136 KB Output is correct
8 Correct 91 ms 6136 KB Output is correct
9 Correct 82 ms 5904 KB Output is correct
10 Correct 82 ms 5892 KB Output is correct
11 Correct 81 ms 6000 KB Output is correct
12 Correct 81 ms 6008 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 496 ms 1036 KB Output is correct
2 Correct 1225 ms 2168 KB Output is correct
3 Correct 1931 ms 2236 KB Output is correct
4 Correct 4234 ms 2424 KB Output is correct
5 Execution timed out 5088 ms 4092 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

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