oj.uz

Submission #170825

# Submission time Handle Problem Language Result Execution time Memory
170825 2019-12-26T13:11:51 Z ZwariowanyMarcin Sterilizing Spray (JOI15_sterilizing) C++14
80 / 100
 5000 ms 9228 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) {
			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 9 ms 1144 KB Output is correct
2 Correct 6 ms 1144 KB Output is correct
3 Correct 4 ms 1144 KB Output is correct
4 Correct 7 ms 1272 KB Output is correct
5 Correct 8 ms 1400 KB Output is correct
6 Correct 7 ms 1272 KB Output is correct
7 Correct 8 ms 1400 KB Output is correct
8 Correct 7 ms 1272 KB Output is correct
9 Correct 8 ms 1364 KB Output is correct
10 Correct 7 ms 1400 KB Output is correct
11 Correct 7 ms 1400 KB Output is correct
12 Correct 7 ms 1400 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1912 KB Output is correct
2 Correct 33 ms 3820 KB Output is correct
3 Correct 38 ms 4016 KB Output is correct
4 Correct 60 ms 3704 KB Output is correct
5 Correct 110 ms 8000 KB Output is correct
6 Correct 109 ms 7800 KB Output is correct
7 Execution timed out 5090 ms 7296 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 5496 KB Output is correct
2 Correct 103 ms 5624 KB Output is correct
3 Correct 120 ms 4728 KB Output is correct
4 Correct 106 ms 4776 KB Output is correct
5 Correct 169 ms 9012 KB Output is correct
6 Correct 180 ms 9020 KB Output is correct
7 Correct 162 ms 8824 KB Output is correct
8 Correct 209 ms 9136 KB Output is correct
9 Correct 174 ms 9204 KB Output is correct
10 Correct 195 ms 9228 KB Output is correct
11 Correct 161 ms 9204 KB Output is correct
12 Correct 233 ms 9080 KB Output is correct