oj.uz

Submission #55367

# Submission time Handle Problem Language Result Execution time Memory
55367 2018-07-07T05:31:32 Z 윤교준(#1546) Employment (JOI16_employment) C++11
10 / 100
 5000 ms 11108 KB 
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[sz(V)-2])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmax(a,b) (a)=max((a),(b))
#define upmin(a,b) (a)=min((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;

const bool debug = false;
const int MAXN = 200005;
const int MAXQ = 200005;
const int SQRN = 485;

int A[MAXN];
int B[MAXQ], C[MAXQ], D[MAXQ];

int N, Q;

struct BUK {
	set<pii> O;
	vector<int> XV;
	int cnt[SQRN*2];
	int S, E;

	void clear() {
		XV.clear();
	}
	void calcnt() {
		auto it = O.begin();
		int vn = sz(XV), n = 0, l = 0;
		for(int vi = vn-1, y; 0 <= vi; vi--) {
			y = XV[vi];
			for(int i; O.end() != it; it++) {
				i = it -> second;
				if(A[i] < y) break;

				n++;
				if(S < i && y <= A[i-1]) l++;
				if(i < E && y < A[i+1]) l++;

				if(debug) {
					printf("vn=%d, vi=%d, y=%d : n=%d, l=%d\n", vn, vi, y, n, l);
				}
			}
			cnt[vi] = n-l;
		}
	}
	void cal() {
		sorv(XV); univ(XV);
		calcnt();
	}
	int get(int y) {
		if(XV.empty() || XV.back() < y) return 0;
		int s = 0, e = sz(XV)-1; for(int m; s < e;) {
			m = (s+e)/2;
			if(y <= XV[m]) e = m;
			else s = m+1;
		}
		return cnt[s];
	}
	void upd(int idx, int x, int y) {
		O.erase(pii(-x, idx));
		O.insert(pii(-y, idx));
		calcnt();
	}

	void print() {
		puts("BUK INF");
		for(int v : XV) printf("%d ", v); puts("");
		for(int i = 0; i < sz(XV); i++) printf("%d ; %d\n", i, cnt[i]);
		puts("BUK INF END");
	}
} buk[SQRN]; int bukn;

void initbuk(int qs) {
	for(int bi = 1, s, e;; bi++) {
		s = (bi-1)*SQRN + 1;
		e = min(N, bi*SQRN);
		if(s > e) break;

		buk[bi].clear();
		for(int i = s; i <= e; i++)
			buk[bi].XV.pb(A[i]);
	}
	for(int qi = qs; qi < qs+SQRN && qi <= Q; qi++) {
		if(2 != B[qi]) continue;
		int bi = (C[qi]-1)/SQRN + 1;
		buk[bi].XV.pb(D[qi]);
	}
	for(int i = 1; i <= 450 && i < SQRN; i++) buk[i].cal();

	if(debug) {
		buk[1].print();
	}
}

void upd(int x, int y) {
	int bi = (x-1)/SQRN + 1;
	int bf = A[x];
	A[x] = y;
	buk[bi].upd(x, bf, y);
}

int CC[SQRN];
int getAns(int y) {
	if(debug) printf("getAns y=%d\n", y);
	int ret = 0;
	for(int bi = 1, s, e; bi <= bukn; bi++) {
		s = buk[bi].S; e = buk[bi].E;
		CC[bi] = buk[bi].get(y);
		ret += CC[bi];

		if(1 < bi && y <= A[s-1] && y <= A[s])
			ret--;

		if(debug) printf("bi=%d, s=%d, e=%d : ret=%d\n", bi, s, e, ret);
	}
	if(debug) printf("FINAL ret=%d\n", ret);
	return ret;
}

int main() {
	if(debug) freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(false);

	cin >> N >> Q;
	for(int i = 1; i <= N; i++) cin >> A[i];
	for(int i = 1; i <= Q; i++) {
		cin >> B[i] >> C[i];
		if(2 == B[i]) cin >> D[i];
	}

	{
		vector<int> V;
		for(int i = 1; i <= N; i++) V.pb(A[i]);
		for(int i =1 ; i <= Q; i++)
			V.pb(1 == B[i] ? C[i] : D[i]);

		sorv(V); univ(V);

		for(int i = 1; i <= N; i++)
			A[i] = (int)(lower_bound(allv(V), A[i]) - V.begin()) + 1;
		for(int i = 1; i <= Q; i++) {
			if(1 == B[i])
				C[i] = (int)(lower_bound(allv(V), C[i]) - V.begin()) + 1;
			else
				D[i] = (int)(lower_bound(allv(V), D[i]) - V.begin()) + 1;
		}
	}

	if(debug) {
		for(int i = 1; i <= N; i++)
			printf("%d ", A[i]);
		puts("");
		for(int i = 1; i <= Q; i++)
			printf("Q %d : %d %d %d\n", i, B[i], C[i], D[i]);
	}

	for(int bi = 1, s, e;; bi++) {
		s = (bi-1)*SQRN+1;
		e = min(N, bi*SQRN);
		if(s > e) break;
		buk[bi].S = s;
		buk[bi].E = e;
		for(int i = s; i <= e; i++)
			buk[bi].O.insert(pii(-A[i], i));
		bukn = bi;
	}

	for(int qi = 1; qi <= Q; qi++) {
		if(1 == qi % SQRN) {
			initbuk(qi);
		}

		if(1 == B[qi]) {
			printf("%d\n", getAns(C[qi]));
		} else {
			upd(C[qi], D[qi]);
		}
	}

	return 0;
}

Compilation message

employment.cpp: In member function 'void BUK::print()':
employment.cpp:83:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for(int v : XV) printf("%d ", v); puts("");
   ^~~
employment.cpp:83:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for(int v : XV) printf("%d ", v); puts("");
                                     ^~~~
employment.cpp: In function 'int main()':
employment.cpp:137:19: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  if(debug) freopen("input.txt", "r", stdin);
            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2260 KB Output is correct
2 Correct 4 ms 2280 KB Output is correct
3 Correct 4 ms 2356 KB Output is correct
4 Correct 9 ms 2408 KB Output is correct
5 Correct 6 ms 2408 KB Output is correct
6 Correct 7 ms 2456 KB Output is correct
7 Correct 12 ms 2456 KB Output is correct
8 Correct 15 ms 2456 KB Output is correct
9 Correct 14 ms 2456 KB Output is correct
10 Correct 19 ms 2588 KB Output is correct
11 Correct 20 ms 2588 KB Output is correct
12 Correct 19 ms 2588 KB Output is correct
13 Correct 19 ms 2588 KB Output is correct
14 Correct 18 ms 2588 KB Output is correct
15 Correct 20 ms 2588 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2588 KB Output is correct
2 Correct 13 ms 2588 KB Output is correct
3 Correct 9 ms 2600 KB Output is correct
4 Correct 153 ms 3436 KB Output is correct
5 Correct 493 ms 4908 KB Output is correct
6 Correct 1096 ms 5580 KB Output is correct
7 Correct 2441 ms 7864 KB Output is correct
8 Correct 3655 ms 8764 KB Output is correct
9 Execution timed out 5061 ms 11108 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2260 KB Output is correct
2 Correct 4 ms 2280 KB Output is correct
3 Correct 4 ms 2356 KB Output is correct
4 Correct 9 ms 2408 KB Output is correct
5 Correct 6 ms 2408 KB Output is correct
6 Correct 7 ms 2456 KB Output is correct
7 Correct 12 ms 2456 KB Output is correct
8 Correct 15 ms 2456 KB Output is correct
9 Correct 14 ms 2456 KB Output is correct
10 Correct 19 ms 2588 KB Output is correct
11 Correct 20 ms 2588 KB Output is correct
12 Correct 19 ms 2588 KB Output is correct
13 Correct 19 ms 2588 KB Output is correct
14 Correct 18 ms 2588 KB Output is correct
15 Correct 20 ms 2588 KB Output is correct
16 Correct 7 ms 2588 KB Output is correct
17 Correct 13 ms 2588 KB Output is correct
18 Correct 9 ms 2600 KB Output is correct
19 Correct 153 ms 3436 KB Output is correct
20 Correct 493 ms 4908 KB Output is correct
21 Correct 1096 ms 5580 KB Output is correct
22 Correct 2441 ms 7864 KB Output is correct
23 Correct 3655 ms 8764 KB Output is correct
24 Execution timed out 5061 ms 11108 KB Time limit exceeded
25 Halted 0 ms 0 KB -