oj.uz

Submission #157052

# Submission time Handle Problem Language Result Execution time Memory
157052 2019-10-09T09:29:56 Z jhwest2 Employment (JOI16_employment) C++14
30 / 100
 689 ms 34176 KB 
#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

struct Query{
	int t, a, b;
} Q[202020];
int N, M;
int A[202020];
vector<int> v;

struct SEG {
	vector<ll> tree, lazy;

	void init(int n) {
		tree.resize(4*n), lazy.resize(4*n);
	}

	void lpush(int lo, int hi, int idx) {
		if (lazy[idx] == 0) return;
		tree[idx] += (hi-lo+1)*lazy[idx];

		if (lo==hi) { lazy[idx] = 0; return; }
		lazy[2*idx] += lazy[idx];
		lazy[2*idx+1] += lazy[idx];
		lazy[idx] = 0; return;
	}

	ll update(int a, int b, int x, int lo, int hi, int idx) {
		lpush(lo, hi, idx);
		if (b<lo || a>hi) return tree[idx];
		if (a<=lo && hi<=b) {
			lazy[idx] += x; lpush(lo, hi, idx);
			return tree[idx];
		}
		return tree[idx] = update(a, b, x, lo, lo+hi>>1, 2*idx) + update(a, b, x, 1+(lo+hi>>1), hi, 2*idx+1);
	}

	ll query(int a, int b, int lo, int hi, int idx) {
		lpush(lo, hi, idx);
		if (b<lo || a>hi) return 0;
		if (a<=lo && hi<=b) return tree[idx];

		return query(a, b, lo, lo+hi>>1, 2*idx) + query(a, b, 1+(lo+hi>>1), hi, 2*idx+1);
	}
} seg;

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);

	cin >> N >> M;
	for (int i=0; i<N; i++) { cin >> A[i]; v.push_back(A[i]); }

	for (int i=0; i<M; i++) {
		cin >> Q[i].t;
		if (Q[i].t == 1) { cin >> Q[i].a; v.push_back(Q[i].a); }
		else { cin >> Q[i].a >> Q[i].b; v.push_back(Q[i].b); }
	}

	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());

	for (int i=0; i<N; i++)
		A[i] = lower_bound(v.begin(), v.end(), A[i])-v.begin();

	for (int i=0; i<M; i++) {
		if (Q[i].t==1) Q[i].a = lower_bound(v.begin(), v.end(), Q[i].a)-v.begin();
		else Q[i].b = lower_bound(v.begin(), v.end(), Q[i].b)-v.begin();
	}

	seg.init(v.size());

	seg.update(0, A[0], 1, 0, v.size(), 1);
	for (int i=1; i<N; i++) {
		if (A[i-1] < A[i]) seg.update(A[i-1]+1, A[i], 1, 0, v.size(), 1);
	}

	for (int i=0; i<M; i++) {
		if (Q[i].t == 1) cout << seg.query(Q[i].a, Q[i].a, 0, v.size(), 1) << '\n';
		else {
			int l, h;
			l = min(A[max(0, Q[i].a-2)], A[min((int)v.size()-1, Q[i].a)]);
			h = max(A[max(0, Q[i].a-2)], A[min((int)v.size()-1, Q[i].a)]);

			if (A[Q[i].a] < Q[i].b) {
				seg.update(A[Q[i].a-1]+1, l, -1, 0, v.size(), 1);
				seg.update(h+1, Q[i].b, 1, 0, v.size(), 1);
				A[Q[i].a-1] = Q[i].b;
			}
			else {
				seg.update(Q[i].b+1, l, 1, 0, v.size(), 1);
				seg.update(h+1, A[Q[i].a-1], -1, 0, v.size(), 1);
				A[Q[i].a-1] = Q[i].b;
			}
		}
	}
}

Compilation message

employment.cpp: In member function 'll SEG::update(int, int, int, int, int, int)':
employment.cpp:40:44: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   return tree[idx] = update(a, b, x, lo, lo+hi>>1, 2*idx) + update(a, b, x, 1+(lo+hi>>1), hi, 2*idx+1);
                                          ~~^~~
employment.cpp:40:82: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   return tree[idx] = update(a, b, x, lo, lo+hi>>1, 2*idx) + update(a, b, x, 1+(lo+hi>>1), hi, 2*idx+1);
                                                                                ~~^~~
employment.cpp: In member function 'll SEG::query(int, int, int, int, int)':
employment.cpp:48:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   return query(a, b, lo, lo+hi>>1, 2*idx) + query(a, b, 1+(lo+hi>>1), hi, 2*idx+1);
                          ~~^~~
employment.cpp:48:62: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   return query(a, b, lo, lo+hi>>1, 2*idx) + query(a, b, 1+(lo+hi>>1), hi, 2*idx+1);
                                                            ~~^~~

Subtask #1
0 / 10.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 5 ms 760 KB Output is correct
3 Correct 5 ms 760 KB Output is correct
4 Correct 27 ms 3320 KB Output is correct
5 Correct 55 ms 6136 KB Output is correct
6 Correct 85 ms 9076 KB Output is correct
7 Correct 143 ms 13620 KB Output is correct
8 Correct 187 ms 17020 KB Output is correct
9 Correct 330 ms 26988 KB Output is correct
10 Correct 308 ms 25160 KB Output is correct
11 Correct 382 ms 30636 KB Output is correct
12 Correct 438 ms 33508 KB Output is correct
13 Correct 689 ms 33512 KB Output is correct
14 Correct 420 ms 33268 KB Output is correct
15 Correct 417 ms 33132 KB Output is correct
16 Correct 434 ms 34152 KB Output is correct
17 Correct 439 ms 34064 KB Output is correct
18 Correct 436 ms 34024 KB Output is correct
19 Correct 431 ms 34076 KB Output is correct
20 Correct 430 ms 34176 KB Output is correct

Subtask #3
0 / 60.0

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