oj.uz

답안 #157053

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
157053 2019-10-09T09:36:28 Z jhwest2 Employment (JOI16_employment) C++14
30 / 100
 549 ms 31592 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)N-1, Q[i].a)]);
			h = max(A[max(0, Q[i].a-2)], A[min((int)N-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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Incorrect 4 ms 564 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 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 28 ms 2936 KB Output is correct
5 Correct 54 ms 5368 KB Output is correct
6 Correct 85 ms 8060 KB Output is correct
7 Correct 140 ms 11988 KB Output is correct
8 Correct 188 ms 14932 KB Output is correct
9 Correct 344 ms 24380 KB Output is correct
10 Correct 325 ms 22560 KB Output is correct
11 Correct 408 ms 27852 KB Output is correct
12 Correct 549 ms 30960 KB Output is correct
13 Correct 446 ms 31108 KB Output is correct
14 Correct 412 ms 30496 KB Output is correct
15 Correct 430 ms 30696 KB Output is correct
16 Correct 423 ms 31560 KB Output is correct
17 Correct 426 ms 31592 KB Output is correct
18 Correct 425 ms 31480 KB Output is correct
19 Correct 430 ms 31592 KB Output is correct
20 Correct 423 ms 31344 KB Output is correct

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Incorrect 4 ms 564 KB Output isn't correct
5 Halted 0 ms 0 KB -