oj.uz

답안 #28892

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
28892 2017-07-17T12:13:19 Z cdemirer 운세 보기 2 (JOI14_fortune_telling2) C++14
35 / 100
 2000 ms 100428 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<pair<int, int> > vii;
typedef vector<vector<pair<int, int> > > vvii;
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)

int twopow[22] = {0};
// x is always 2
int mypow(int x, int e) {
	if (twopow[e]) return twopow[e];
	if (e == 0) return 1;
	int a = mypow(x, e/2);
	return (twopow[e] = (e % 2 == 0) ? a*a : a*a*x);
}

int N, K;
vii cisimler;
map<int, int> tbl;
map<int, int> revtbl;
int queries[200002];
vii qs;
int rmqtbl[200002][19];
int rminqtbl[200002][19];
vii tickets;
bool kucuk[200002];
int lg2[270000];

int rmq(int a, int b) {
	//cerr << "max of: ";
	//for (int i = a; i <= b; i++) {
		//cerr << rmqtbl[i][0] << " ";
	//}
	int pop = b - a + 1;
	int e = (int)lg2[pop];
	int a2 = b - mypow(2, e) + 1;
	return max(rmqtbl[a][e], rmqtbl[a2][e]);
}
int rminq(int a, int b) {
	int pop = b - a + 1;
	int e = (int)lg2[pop];
	int a2 = b - mypow(2, e) + 1;
	return min(rminqtbl[a][e], rminqtbl[a2][e]);
}
int binsrc(int x) {
	int l = 0, r = K;
	while (r > l) {
		int mid = (l + r) / 2;
		if (qs[mid].first >= x) r = mid;
		else l = mid+1;
	}
	return l;
}

int bit[524289] = {0};
void bitinc(int x) {
	x += 2;
	while (x <= 524288) {
		bit[x]++;
		x += x & -x;
	}
}
int bitget(int x) {
	x += 2;
	int sum = 0;
	while (x > 0) {
		sum += bit[x];
		x -= x & -x;
	}
	return sum;
}

int main(int argc, char **argv) {

	//freopen("input", "r", stdin);
	//freopen("output", "w", stdout);

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int lgcur = 1;
	for (int i = 1; i < 19; i++) {
		int lim = mypow(2, i);
		for ( ; lgcur < lim; lgcur++) {
			lg2[lgcur] = i-1;
		}
	}

	cin >> N >> K;
	set<int> S;
	for (int i = 0; i < N; i++) {
		int a, b; cin >> a >> b;
		cisimler.pb(mp(a, b));
		S.insert(a);
		S.insert(b);
	}
	for (int i = 0; i < K; i++) {
		int a; cin >> a;
		queries[i] = a;
		qs.pb(mp(a, i));
		S.insert(a);
	}
	int c = 0;
	while ( ! S.empty() ) {
		int x = *S.begin();
		S.erase(S.begin());
		tbl[x] = c;
		revtbl[c] = x;
		c++;
	}
	for (int i = 0; i < N; i++) {
		cisimler[i].first = tbl[cisimler[i].first];
		cisimler[i].second = tbl[cisimler[i].second];
		//cerr << i << " " << revtbl[cisimler[i].first] << " " << revtbl[cisimler[i].second] << "\n";
	}
	for (int i = 0; i < K; i++) {
		queries[i] = tbl[queries[i]];
		qs[i].first = tbl[qs[i].first];
	}
	sort(qs.begin(), qs.end());
	for (int i = 0; i < K; i++) {
		rmqtbl[i][0] = qs[i].second;
		rminqtbl[i][0] = qs[i].second;
	}
	for (int e = 1; e < 18; e++) {
		int off = mypow(2, e-1);
		for (int i = 0; i < K; i++) {
			if (i+2*off > K) break;
			rmqtbl[i][e] = max(rmqtbl[i][e-1], rmqtbl[i+off][e-1]);
			rminqtbl[i][e] = min(rminqtbl[i][e-1], rminqtbl[i+off][e-1]);
		}
	}
	for (int i = 0; i < N; i++) {
		int cmin = min(cisimler[i].first, cisimler[i].second);
		int cmax = max(cisimler[i].first, cisimler[i].second);
		int ls = binsrc(cmin);
		//cerr << cmin << endl;
		int hs = binsrc(cmax);
		if (ls == K) {
			kucuk[i] = (cmin == cisimler[i].first);
			continue;
		} 
		if (hs == K) {
			kucuk[i] = false;
			continue;
		}
		//cerr << "ls : " << ls << " hs : " << hs << endl;
		if (ls != hs) {
			int q = rmq(ls, hs-1);
			//cerr << " is " << q << endl;
			tickets.pb(mp(q+1, i));
		}
	 	else {
			int q = rminq(ls, K-1);
			//cerr << ls << " " << q << endl;
			if (cmin == cisimler[i].first) {
				tickets.pb(mp(q+1, i));
			}
			else {
				tickets.pb(mp(q, i));
			}
		}
	}
	/*for (int i = 0; i < tickets.size(); i++) {
		cerr << tickets[i].first << " " << tickets[i].second << endl;
	}*/
	int cur = K;
	int tot = 0;
	sort(tickets.begin(), tickets.end());
	for (int i = tickets.size()-1; i >= 0; i--) {
		int x = tickets[i].second;
		while (cur > tickets[i].first) {
			cur--;
			bitinc(queries[cur]);
			tot++;
		}
		int lim = max(cisimler[x].first, cisimler[x].second);
		int a = tot - bitget(lim-1);
		//if (x == 3) cerr << lim << "\n";
		kucuk[x] = (a % 2 == 1);
	}
	ll sum = 0;
	for (int i = 0; i < N; i++) {
		//cerr << kucuk[i] << endl;
		if (kucuk[i]) {
			sum += revtbl[ min(cisimler[i].first, cisimler[i].second) ];
		}
		else {
			sum += revtbl[ max(cisimler[i].first, cisimler[i].second) ];
		}
	}
	cout << sum << endl;

	return 0;
}

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 36088 KB Output is correct
2 Correct 0 ms 36088 KB Output is correct
3 Correct 3 ms 36220 KB Output is correct
4 Correct 3 ms 36220 KB Output is correct
5 Correct 3 ms 36220 KB Output is correct
6 Correct 3 ms 36220 KB Output is correct
7 Correct 3 ms 36220 KB Output is correct
8 Correct 0 ms 36220 KB Output is correct
9 Correct 3 ms 36220 KB Output is correct
10 Correct 3 ms 36088 KB Output is correct
11 Correct 0 ms 36088 KB Output is correct
12 Correct 3 ms 36088 KB Output is correct
13 Correct 0 ms 36088 KB Output is correct

Subtask #2
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 39192 KB Output is correct
2 Correct 123 ms 42520 KB Output is correct
3 Correct 246 ms 45332 KB Output is correct
4 Correct 336 ms 49300 KB Output is correct
5 Correct 289 ms 49300 KB Output is correct
6 Correct 303 ms 49300 KB Output is correct
7 Correct 296 ms 49300 KB Output is correct
8 Correct 286 ms 49296 KB Output is correct
9 Correct 169 ms 45548 KB Output is correct
10 Correct 106 ms 43672 KB Output is correct
11 Correct 123 ms 42268 KB Output is correct
12 Correct 166 ms 46620 KB Output is correct
13 Correct 149 ms 44924 KB Output is correct
14 Correct 206 ms 45556 KB Output is correct
15 Correct 179 ms 45548 KB Output is correct
16 Correct 256 ms 47420 KB Output is correct

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 639 ms 58924 KB Output is correct
2 Correct 1153 ms 67700 KB Output is correct
3 Correct 1656 ms 78608 KB Output is correct
4 Execution timed out 2000 ms 100428 KB Execution timed out
5 Halted 0 ms 0 KB -