oj.uz

Submission #55382

# Submission time Handle Problem Language Result Execution time Memory
55382 2018-07-07T06:03:52 Z 윤교준(#1546) Employment (JOI16_employment) C++11
10 / 100
 5000 ms 12492 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() {
		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;

vector<int> QXV[SQRN];
void initbuk(int qs) {
	for(int bi = 1; bi <= bukn; bi++) {
		QXV[bi].clear();
		buk[bi].clear();
	}

	for(int qi = qs; qi < qs+SQRN && qi <= Q; qi++) {
		if(2 != B[qi]) continue;
		int bi = (C[qi]-1)/SQRN + 1;
		QXV[bi].pb(D[qi]);
	}

	for(int bi = 1; bi <= bukn; bi++) {
		vector<int> V;
		for(auto &v : buk[bi].O)
			V.pb(-v.first);
		revv(V); univ(V);

		sorv(QXV[bi]); univ(QXV[bi]);

		vector<int> &T = buk[bi].XV;
		for(int a = 0, b = 0, an = sz(V), bn = sz(QXV[bi]); a < an || b < bn;) {
			if(a < an && (b == bn || V[a] <= QXV[bi][b])) {
				if(T.empty() || T.back() != V[a]) T.pb(V[a]);
				a++;
			} else {
				if(T.empty() || T.back() != QXV[bi][b])
					T.pb(QXV[bi][b]);
				b++;
			}
		}
	}

	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:79:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for(int v : XV) printf("%d ", v); puts("");
   ^~~
employment.cpp:79: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:170: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 2424 KB Output is correct
2 Correct 3 ms 2432 KB Output is correct
3 Correct 4 ms 2432 KB Output is correct
4 Correct 9 ms 3332 KB Output is correct
5 Correct 7 ms 3332 KB Output is correct
6 Correct 6 ms 3332 KB Output is correct
7 Correct 13 ms 3660 KB Output is correct
8 Correct 16 ms 3660 KB Output is correct
9 Correct 15 ms 3660 KB Output is correct
10 Correct 19 ms 3660 KB Output is correct
11 Correct 20 ms 3660 KB Output is correct
12 Correct 19 ms 3660 KB Output is correct
13 Correct 18 ms 3660 KB Output is correct
14 Correct 21 ms 3660 KB Output is correct
15 Correct 19 ms 3660 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3660 KB Output is correct
2 Correct 9 ms 3660 KB Output is correct
3 Correct 9 ms 3660 KB Output is correct
4 Correct 77 ms 4400 KB Output is correct
5 Correct 213 ms 5848 KB Output is correct
6 Correct 473 ms 6524 KB Output is correct
7 Correct 1219 ms 8792 KB Output is correct
8 Correct 2062 ms 10032 KB Output is correct
9 Execution timed out 5018 ms 12492 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 2424 KB Output is correct
2 Correct 3 ms 2432 KB Output is correct
3 Correct 4 ms 2432 KB Output is correct
4 Correct 9 ms 3332 KB Output is correct
5 Correct 7 ms 3332 KB Output is correct
6 Correct 6 ms 3332 KB Output is correct
7 Correct 13 ms 3660 KB Output is correct
8 Correct 16 ms 3660 KB Output is correct
9 Correct 15 ms 3660 KB Output is correct
10 Correct 19 ms 3660 KB Output is correct
11 Correct 20 ms 3660 KB Output is correct
12 Correct 19 ms 3660 KB Output is correct
13 Correct 18 ms 3660 KB Output is correct
14 Correct 21 ms 3660 KB Output is correct
15 Correct 19 ms 3660 KB Output is correct
16 Correct 8 ms 3660 KB Output is correct
17 Correct 9 ms 3660 KB Output is correct
18 Correct 9 ms 3660 KB Output is correct
19 Correct 77 ms 4400 KB Output is correct
20 Correct 213 ms 5848 KB Output is correct
21 Correct 473 ms 6524 KB Output is correct
22 Correct 1219 ms 8792 KB Output is correct
23 Correct 2062 ms 10032 KB Output is correct
24 Execution timed out 5018 ms 12492 KB Time limit exceeded
25 Halted 0 ms 0 KB -