oj.uz

Submission #28887

# Submission time Handle Problem Language Result Execution time Memory
28887 2017-07-17T12:04:27 Z cdemirer Fortune Telling 2 (JOI14_fortune_telling2) C++14
35 / 100
 2000 ms 99384 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 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)log2(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)log2(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);

	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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 35044 KB Output is correct
2 Correct 0 ms 35044 KB Output is correct
3 Correct 3 ms 35176 KB Output is correct
4 Correct 3 ms 35176 KB Output is correct
5 Correct 3 ms 35176 KB Output is correct
6 Correct 3 ms 35176 KB Output is correct
7 Correct 3 ms 35176 KB Output is correct
8 Correct 3 ms 35176 KB Output is correct
9 Correct 0 ms 35176 KB Output is correct
10 Correct 0 ms 35044 KB Output is correct
11 Correct 0 ms 35044 KB Output is correct
12 Correct 0 ms 35044 KB Output is correct
13 Correct 0 ms 35044 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 38148 KB Output is correct
2 Correct 143 ms 41476 KB Output is correct
3 Correct 223 ms 44288 KB Output is correct
4 Correct 293 ms 48256 KB Output is correct
5 Correct 323 ms 48256 KB Output is correct
6 Correct 286 ms 48256 KB Output is correct
7 Correct 303 ms 48256 KB Output is correct
8 Correct 296 ms 48252 KB Output is correct
9 Correct 149 ms 44504 KB Output is correct
10 Correct 133 ms 42628 KB Output is correct
11 Correct 119 ms 41224 KB Output is correct
12 Correct 186 ms 45576 KB Output is correct
13 Correct 183 ms 43880 KB Output is correct
14 Correct 216 ms 44512 KB Output is correct
15 Correct 176 ms 44504 KB Output is correct
16 Correct 266 ms 46376 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 656 ms 57880 KB Output is correct
2 Correct 1022 ms 66656 KB Output is correct
3 Correct 1573 ms 77564 KB Output is correct
4 Execution timed out 2000 ms 99384 KB Execution timed out
5 Halted 0 ms 0 KB -