oj.uz

Submission #170826

# Submission time Handle Problem Language Result Execution time Memory
170826 2019-12-26T13:13:22 Z ZwariowanyMarcin Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 298 ms 9252 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define ss(x) (int) x.size()
#define pb push_back
#define ll long long
#define cat(x) cerr << #x << " = " << x << endl
#define FOR(i, n) for(int i = 0; i < n; ++i)

using namespace std;	

const int nax = 1e5 + 111;

struct fen {
	ll t[nax];
	
	void init() {
		for(int i = 0; i < nax; ++i)
			t[i] = 0;
	}
	
	void add(int x, int c) {
		for(;x < nax; x += x & -x)
			t[x] += c;
	}
	
	ll query(int x) {
		ll res = 0;
		for(; 0 < x; x -= x & -x)
			res += t[x];
		return res;
	}
	
	ll sum(int l, int r) {
		return query(r) - query(l - 1);
	}
} ja;

set <int> secik;
int n, q, k;
int a[nax];
vector <int> del;

int main() {
	ja.init();
	scanf("%d %d %d", &n, &q, &k);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", a + i);
		secik.insert(i);
		ja.add(i, a[i]);
	}
	for(int i = 1; i <= q; ++i) {
		int type, l, r;
		scanf("%d %d %d", &type, &l, &r);
		if(type == 1) {
			if(!a[l]) secik.insert(l);
			ja.add(l, -a[l]);
			a[l] = r;
			ja.add(l, a[l]);
		}
		if(type == 2) {
			if(k == 1) continue;
			auto it = secik.lower_bound(l);
			while(it != secik.end() && *it <= r) {
				int diff = a[*it] - a[*it] / k;
				ja.add(*it, -diff);
				a[*it] += -diff;
				if(a[*it] == 0)
					del.pb(*it);
				it++;
			}
			for(auto it : del)
				secik.erase(it);
			del.clear();
		}
		if(type == 3) {
			printf("%lld\n", ja.sum(l, r));
		}
	}
				
				
	
	return 0;
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &q, &k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", a + i);
   ~~~~~^~~~~~~~~~~~~
sterilizing.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &type, &l, &r);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1144 KB Output is correct
2 Correct 3 ms 1148 KB Output is correct
3 Correct 4 ms 1272 KB Output is correct
4 Correct 7 ms 1272 KB Output is correct
5 Correct 8 ms 1272 KB Output is correct
6 Correct 7 ms 1272 KB Output is correct
7 Correct 7 ms 1400 KB Output is correct
8 Correct 8 ms 1404 KB Output is correct
9 Correct 8 ms 1272 KB Output is correct
10 Correct 7 ms 1400 KB Output is correct
11 Correct 7 ms 1372 KB Output is correct
12 Correct 7 ms 1372 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 4828 KB Output is correct
2 Correct 56 ms 4792 KB Output is correct
3 Correct 70 ms 7044 KB Output is correct
4 Correct 89 ms 8668 KB Output is correct
5 Correct 98 ms 9252 KB Output is correct
6 Correct 99 ms 9204 KB Output is correct
7 Correct 98 ms 9080 KB Output is correct
8 Correct 99 ms 9080 KB Output is correct
9 Correct 95 ms 9080 KB Output is correct
10 Correct 96 ms 9080 KB Output is correct
11 Correct 97 ms 9156 KB Output is correct
12 Correct 95 ms 9080 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1656 KB Output is correct
2 Correct 35 ms 3704 KB Output is correct
3 Correct 37 ms 3748 KB Output is correct
4 Correct 60 ms 2680 KB Output is correct
5 Correct 108 ms 6776 KB Output is correct
6 Correct 114 ms 6668 KB Output is correct
7 Correct 95 ms 7108 KB Output is correct
8 Correct 110 ms 7928 KB Output is correct
9 Correct 101 ms 8180 KB Output is correct
10 Correct 100 ms 8024 KB Output is correct
11 Correct 98 ms 8052 KB Output is correct
12 Correct 105 ms 8052 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 4344 KB Output is correct
2 Correct 107 ms 4412 KB Output is correct
3 Correct 117 ms 3704 KB Output is correct
4 Correct 106 ms 3452 KB Output is correct
5 Correct 169 ms 7032 KB Output is correct
6 Correct 181 ms 7024 KB Output is correct
7 Correct 161 ms 6904 KB Output is correct
8 Correct 213 ms 6892 KB Output is correct
9 Correct 184 ms 6904 KB Output is correct
10 Correct 207 ms 7424 KB Output is correct
11 Correct 186 ms 7028 KB Output is correct
12 Correct 298 ms 7160 KB Output is correct