oj.uz

Submission #55378

# Submission time Handle Problem Language Result Execution time Memory
55378 2018-07-07T05:52:56 Z 윤교준(#1546) Employment (JOI16_employment) C++11
10 / 100
 5000 ms 12304 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 YI[SQRN][SQRN];

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(y < 0 || sz(XV) <= y) return 0;
		return cnt[y];
	}
	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 <= bukn; i++) buk[i].cal();

	{
		vector<pii> V;
		for(int qi = qs; qi < qs+SQRN && qi <= Q; qi++) {
			if(1 == B[qi]) V.eb(C[qi], qi);
			else V.eb(D[qi], qi);
		}
		sorv(V);

		for(int bi = 1; bi <= bukn; bi++) {
			int i = 0, n = sz(buk[bi].XV);
			for(auto &v : V) {
				int idx, y; tie(y, idx) = v;
				for(; i < n && buk[bi].XV[i] < y; i++);
				YI[idx-qs][bi] = i;
			}
		}
	}

	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 qs, int qi, 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(YI[qi-qs][bi]);
		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, qs = 1; qi <= Q; qi++) {
		if(1 == qi % SQRN) {
			qs = qi;
			initbuk(qi);
		}

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

	return 0;
}

Compilation message

employment.cpp: In member function 'void BUK::print()':
employment.cpp:80:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for(int v : XV) printf("%d ", v); puts("");
   ^~~
employment.cpp:80: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:152: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 4 ms 2296 KB Output is correct
2 Correct 4 ms 2376 KB Output is correct
3 Correct 3 ms 2376 KB Output is correct
4 Correct 8 ms 3456 KB Output is correct
5 Correct 5 ms 3456 KB Output is correct
6 Correct 6 ms 3456 KB Output is correct
7 Correct 12 ms 3512 KB Output is correct
8 Correct 11 ms 3512 KB Output is correct
9 Correct 13 ms 3512 KB Output is correct
10 Correct 17 ms 3532 KB Output is correct
11 Correct 18 ms 3532 KB Output is correct
12 Correct 17 ms 3532 KB Output is correct
13 Correct 18 ms 3532 KB Output is correct
14 Correct 18 ms 3532 KB Output is correct
15 Correct 18 ms 3540 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3540 KB Output is correct
2 Correct 9 ms 3668 KB Output is correct
3 Correct 7 ms 3668 KB Output is correct
4 Correct 74 ms 4428 KB Output is correct
5 Correct 286 ms 5924 KB Output is correct
6 Correct 778 ms 6404 KB Output is correct
7 Correct 1517 ms 8780 KB Output is correct
8 Correct 2719 ms 10028 KB Output is correct
9 Execution timed out 5011 ms 12304 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2296 KB Output is correct
2 Correct 4 ms 2376 KB Output is correct
3 Correct 3 ms 2376 KB Output is correct
4 Correct 8 ms 3456 KB Output is correct
5 Correct 5 ms 3456 KB Output is correct
6 Correct 6 ms 3456 KB Output is correct
7 Correct 12 ms 3512 KB Output is correct
8 Correct 11 ms 3512 KB Output is correct
9 Correct 13 ms 3512 KB Output is correct
10 Correct 17 ms 3532 KB Output is correct
11 Correct 18 ms 3532 KB Output is correct
12 Correct 17 ms 3532 KB Output is correct
13 Correct 18 ms 3532 KB Output is correct
14 Correct 18 ms 3532 KB Output is correct
15 Correct 18 ms 3540 KB Output is correct
16 Correct 7 ms 3540 KB Output is correct
17 Correct 9 ms 3668 KB Output is correct
18 Correct 7 ms 3668 KB Output is correct
19 Correct 74 ms 4428 KB Output is correct
20 Correct 286 ms 5924 KB Output is correct
21 Correct 778 ms 6404 KB Output is correct
22 Correct 1517 ms 8780 KB Output is correct
23 Correct 2719 ms 10028 KB Output is correct
24 Execution timed out 5011 ms 12304 KB Time limit exceeded
25 Halted 0 ms 0 KB -