답안 #55383 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
55383	2018-07-07T06:11:44 Z	윤교준(#1546)	Employment (JOI16_employment)	C++11	0 / 100	5000 ms	19072 KB

employment

#include <bits/stdc++.h>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
#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;
int rd(int s, int e) { return rand()%(e-s+1) + s; }
static unsigned char str[55000055], *p = str;

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

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+512 && qi <= Q; qi++) {
		if(2 != B[qi]) continue;
		int bi = ((C[qi]-1)>>9) + 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+512 && 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)>>9) + 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(0) {
		freopen("output.txt", "w", stdout);
		srand(time(0));
		puts("200000 200000");
		for(int i = 0; i < 200000; i++)
			printf("%d\n", rd(1, 1000000000));
		for(int i = 0; i < 200000; i++) {
			if(rd(0, 1)) {
				printf("1 %d\n", rd(1, 1000000000));
			} else {
				printf("2 %d %d\n", rd(1, 200000), rd(1, 1000000000));
			}
		}
		return 0;
	}

	//freopen("output.txt", "r", stdin);
	//freopen("tmp.txt", "w", stdout);
	fread(str, 1, 55000055, stdin);
	rf(N) rf(Q)
	for(int i = 1; i <= N; i++) { rf(A[i]); }
	for(int i = 1; i <= Q; i++) {
		rf(B[i]) rf(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)<<9)+1;
		e = min(N, bi<<9);
		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 & 511)) {
			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:82:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for(int v : XV) printf("%d ", v); puts("");
   ^~~
employment.cpp:82: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:174:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen("output.txt", "w", stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
employment.cpp:191:7: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  fread(str, 1, 55000055, stdin);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	3 ms	2424 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	3816 KB	Output is correct
2	Correct	8 ms	3872 KB	Output is correct
3	Correct	8 ms	3872 KB	Output is correct
4	Correct	53 ms	5004 KB	Output is correct
5	Correct	196 ms	6776 KB	Output is correct
6	Correct	431 ms	7932 KB	Output is correct
7	Correct	998 ms	10668 KB	Output is correct
8	Correct	1558 ms	12120 KB	Output is correct
9	Correct	3525 ms	16228 KB	Output is correct
10	Correct	4032 ms	18748 KB	Output is correct
11	Execution timed out	5054 ms	19072 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Subtask #3
0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	3 ms	2424 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

답안 #55383

Compilation message

Subtask #1 0 / 10.0

Subtask #2 0 / 30.0

Subtask #3 0 / 60.0

Subtask #1
0 / 10.0

Subtask #2
0 / 30.0

Subtask #3
0 / 60.0