oj.uz

Submission #55360

# Submission time Handle Problem Language Result Execution time Memory
55360 2018-07-07T05:24:33 Z 윤교준(#1546) Employment (JOI16_employment) C++11
10 / 100
 5000 ms 6616 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], AO[MAXN];
int B[MAXQ], C[MAXQ], D[MAXQ];

int N, Q;

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

	void clear() {
		XV.clear();
	}
	void calcnt() {
		int vn = sz(XV), n = 0, l = 0;
		for(int vi = vn-1, y, oi = S; 0 <= vi; vi--) {
			y = XV[vi];
			for(int i; oi <= E; oi++) {
				i = AO[oi];
				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, oi = %d : n=%d, l=%d\n", vn, vi, y, oi, 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() {
		sort(AO+S, AO+E+1, [&](int a, int b) {
			if(A[a] != A[b]) return A[a] > A[b];
			return a < b;
		});
		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;
	A[x] = y;
	buk[bi].upd();
}

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]);
	}

	iota(AO, AO+N+1, 0);
	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;
		sort(AO+s, AO+e+1, [&](int a, int b) {
			if(A[a] != A[b]) return A[a] > A[b];
			return a < b;
		});
		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:136: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 2168 KB Output is correct
2 Correct 3 ms 2276 KB Output is correct
3 Correct 3 ms 2328 KB Output is correct
4 Correct 10 ms 2388 KB Output is correct
5 Correct 5 ms 2388 KB Output is correct
6 Correct 6 ms 2564 KB Output is correct
7 Correct 13 ms 2564 KB Output is correct
8 Correct 12 ms 2608 KB Output is correct
9 Correct 13 ms 2608 KB Output is correct
10 Correct 18 ms 2608 KB Output is correct
11 Correct 20 ms 2608 KB Output is correct
12 Correct 19 ms 2608 KB Output is correct
13 Correct 21 ms 2608 KB Output is correct
14 Correct 18 ms 2660 KB Output is correct
15 Correct 20 ms 2660 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2660 KB Output is correct
2 Correct 9 ms 2660 KB Output is correct
3 Correct 8 ms 2660 KB Output is correct
4 Correct 107 ms 3072 KB Output is correct
5 Correct 344 ms 3348 KB Output is correct
6 Correct 757 ms 3804 KB Output is correct
7 Correct 1799 ms 4556 KB Output is correct
8 Correct 2970 ms 5000 KB Output is correct
9 Execution timed out 5015 ms 6616 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 2168 KB Output is correct
2 Correct 3 ms 2276 KB Output is correct
3 Correct 3 ms 2328 KB Output is correct
4 Correct 10 ms 2388 KB Output is correct
5 Correct 5 ms 2388 KB Output is correct
6 Correct 6 ms 2564 KB Output is correct
7 Correct 13 ms 2564 KB Output is correct
8 Correct 12 ms 2608 KB Output is correct
9 Correct 13 ms 2608 KB Output is correct
10 Correct 18 ms 2608 KB Output is correct
11 Correct 20 ms 2608 KB Output is correct
12 Correct 19 ms 2608 KB Output is correct
13 Correct 21 ms 2608 KB Output is correct
14 Correct 18 ms 2660 KB Output is correct
15 Correct 20 ms 2660 KB Output is correct
16 Correct 6 ms 2660 KB Output is correct
17 Correct 9 ms 2660 KB Output is correct
18 Correct 8 ms 2660 KB Output is correct
19 Correct 107 ms 3072 KB Output is correct
20 Correct 344 ms 3348 KB Output is correct
21 Correct 757 ms 3804 KB Output is correct
22 Correct 1799 ms 4556 KB Output is correct
23 Correct 2970 ms 5000 KB Output is correct
24 Execution timed out 5015 ms 6616 KB Time limit exceeded
25 Halted 0 ms 0 KB -