Submission #28904

# Submission time Handle Problem Language Result Execution time Memory
28904 2017-07-17T14:42:28 Z cdemirer Fortune Telling 2 (JOI14_fortune_telling2) C++14
35 / 100
1863 ms 107476 KB
#include <bits/stdc++.h>
//#include <unordered_map>
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;
unordered_map<int, int> tbl;
unordered_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;
}
# Verdict Execution time Memory Grader output
1 Correct 0 ms 36096 KB Output is correct
2 Correct 3 ms 36236 KB Output is correct
3 Correct 3 ms 36228 KB Output is correct
4 Correct 3 ms 36228 KB Output is correct
5 Correct 3 ms 36228 KB Output is correct
6 Correct 3 ms 36228 KB Output is correct
7 Correct 3 ms 36224 KB Output is correct
8 Correct 3 ms 36228 KB Output is correct
9 Correct 3 ms 36228 KB Output is correct
10 Correct 0 ms 36092 KB Output is correct
11 Correct 3 ms 36240 KB Output is correct
12 Correct 3 ms 36236 KB Output is correct
13 Correct 3 ms 36244 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 39 ms 39160 KB Output is correct
2 Correct 86 ms 42656 KB Output is correct
3 Correct 163 ms 46008 KB Output is correct
4 Correct 213 ms 49376 KB Output is correct
5 Correct 173 ms 49380 KB Output is correct
6 Correct 253 ms 49408 KB Output is correct
7 Correct 246 ms 49248 KB Output is correct
8 Correct 239 ms 49396 KB Output is correct
9 Correct 96 ms 46324 KB Output is correct
10 Correct 93 ms 43432 KB Output is correct
11 Correct 73 ms 42168 KB Output is correct
12 Correct 109 ms 47148 KB Output is correct
13 Correct 173 ms 45664 KB Output is correct
14 Correct 189 ms 46212 KB Output is correct
15 Correct 169 ms 46100 KB Output is correct
16 Correct 186 ms 47204 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 586 ms 59352 KB Output is correct
2 Correct 936 ms 70920 KB Output is correct
3 Correct 1099 ms 80312 KB Output is correct
4 Incorrect 1863 ms 107476 KB Output isn't correct
5 Halted 0 ms 0 KB -