oj.uz

답안 #157054

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
157054 2019-10-09T09:41:07 Z jhwest2 Employment (JOI16_employment) C++14
30 / 100
 483 ms 31588 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-1] < Q[i].b) {
				seg.update(A[Q[i].a-1]+1, min(l, Q[i].b), -1, 0, v.size(), 1);
				seg.update(max(h, A[Q[i].a-1])+1, Q[i].b, 1, 0, v.size(), 1);
				A[Q[i].a-1] = Q[i].b;
			}
			else {
				seg.update(Q[i].b+1, min(l, A[Q[i].a-1]), 1, 0, v.size(), 1);
				seg.update(max(h, Q[i].b)+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 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Incorrect 4 ms 632 KB Output isn't correct
8 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 26 ms 2936 KB Output is correct
5 Correct 57 ms 5340 KB Output is correct
6 Correct 92 ms 8052 KB Output is correct
7 Correct 139 ms 11976 KB Output is correct
8 Correct 178 ms 14960 KB Output is correct
9 Correct 313 ms 24552 KB Output is correct
10 Correct 298 ms 22376 KB Output is correct
11 Correct 366 ms 27944 KB Output is correct
12 Correct 421 ms 30904 KB Output is correct
13 Correct 424 ms 31016 KB Output is correct
14 Correct 422 ms 30564 KB Output is correct
15 Correct 411 ms 30596 KB Output is correct
16 Correct 429 ms 31344 KB Output is correct
17 Correct 483 ms 31436 KB Output is correct
18 Correct 436 ms 31476 KB Output is correct
19 Correct 438 ms 31564 KB Output is correct
20 Correct 430 ms 31588 KB Output is correct

Subtask #3
0 / 60.0

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