oj.uz

답안 #157055

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
157055 2019-10-09T09:56:44 Z jhwest2 Employment (JOI16_employment) C++14
30 / 100
 467 ms 31596 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=1; 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=1; 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());

	A[0] = -1; A[N+1] = 2e9;
	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[Q[i].a-1], A[Q[i].a+1]);
			h = max(A[Q[i].a-1], A[Q[i].a+1]);

			if (A[Q[i].a] < Q[i].b) {
				seg.update(A[Q[i].a]+1, min(l, Q[i].b), -1, 0, v.size(), 1);
				seg.update(max(h, A[Q[i].a])+1, Q[i].b, 1, 0, v.size(), 1);
				A[Q[i].a] = Q[i].b;
			}
			else {
				seg.update(Q[i].b+1, min(l, A[Q[i].a]), 1, 0, v.size(), 1);
				seg.update(max(h, Q[i].b)+1, A[Q[i].a], -1, 0, v.size(), 1);
				A[Q[i].a] = 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 3 ms 504 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 27 ms 3064 KB Output is correct
5 Correct 54 ms 5368 KB Output is correct
6 Correct 85 ms 8052 KB Output is correct
7 Correct 148 ms 12068 KB Output is correct
8 Correct 197 ms 14996 KB Output is correct
9 Correct 351 ms 24472 KB Output is correct
10 Correct 323 ms 22376 KB Output is correct
11 Correct 374 ms 27888 KB Output is correct
12 Correct 423 ms 30912 KB Output is correct
13 Correct 467 ms 31148 KB Output is correct
14 Correct 417 ms 30524 KB Output is correct
15 Correct 446 ms 30708 KB Output is correct
16 Correct 438 ms 31548 KB Output is correct
17 Correct 431 ms 31596 KB Output is correct
18 Correct 428 ms 31344 KB Output is correct
19 Correct 432 ms 31464 KB Output is correct
20 Correct 429 ms 31464 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 3 ms 504 KB Output isn't correct
5 Halted 0 ms 0 KB -