oj.uz

Submission #28891

# Submission time Handle Problem Language Result Execution time Memory
28891 2017-07-17T12:12:29 Z cdemirer Fortune Telling 2 (JOI14_fortune_telling2) C++14
35 / 100
 706 ms 58648 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[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)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 < 18; 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

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 38916 KB Output is correct
2 Correct 89 ms 42244 KB Output is correct
3 Correct 183 ms 45056 KB Output is correct
4 Correct 273 ms 49024 KB Output is correct
5 Correct 296 ms 49024 KB Output is correct
6 Correct 326 ms 49024 KB Output is correct
7 Correct 326 ms 49024 KB Output is correct
8 Correct 293 ms 49020 KB Output is correct
9 Correct 166 ms 45272 KB Output is correct
10 Correct 133 ms 43396 KB Output is correct
11 Correct 123 ms 41992 KB Output is correct
12 Correct 169 ms 46344 KB Output is correct
13 Correct 159 ms 44648 KB Output is correct
14 Correct 223 ms 45280 KB Output is correct
15 Correct 193 ms 45272 KB Output is correct
16 Correct 256 ms 47144 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 706 ms 58648 KB Output isn't correct
2 Halted 0 ms 0 KB -