oj.uz

Submission #36098

# Submission time Handle Problem Language Result Execution time Memory
36098 2017-12-05T13:04:56 Z UncleGrandpa925 Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 419 ms 50948 KB 
/*input
5 3
4 6
9 1
8 8
4 2
3 7
8
2
9
*/
#include <bits/stdc++.h>
using namespace std;
#define sp ' '
#define endl '\n'
#define fi first
#define se second
#define mp make_pair
#define int long long
#define N 200010
#define bit(x,y) ((x>>y)&1LL)
#define na(x) (#x) << ":" << x
ostream& operator << (ostream &os, vector<int>&x) {
	for (int i = 0; i < x.size(); i++) os << x[i] << sp;
	return os;
}
ostream& operator << (ostream &os, pair<int, int> x) {
	cout << x.fi << sp << x.se << sp;
	return os;
}
ostream& operator << (ostream &os, vector<pair<int, int> >&x) {
	for (int i = 0; i < x.size(); i++) os << x[i] << endl;
	return os;
}
struct data {
	int fi, se, state;
	data(int _fi, int _se, int _state): fi(_fi), se(_se), state(_state) {};
};

int n, q;
vector<data> a;
vector<pair<int, int> > query;
int tree[N];
int rmq[N][20];
int lg2[N];

bool cmp(data x, data y) {
	return x.se > y.se;
}

void update(int i, int val) {
	for (; i; i -= i & -i) tree[i] += val;
}

int get(int i) {
	int ret = 0;
	for (; i <= N - 5; i += i & -i) ret += tree[i];
	return ret;
}

void initRMQ() {
	for (int i = 1; i <= q; i++) rmq[i][0] = query[i].se;
	for (int k = 1; k <= 20; k++) {
		for (int i = 1; i + (1 << k) - 1 <= q; i++) {
			rmq[i][k] = max(rmq[i][k - 1], rmq[i + (1 << (k - 1))][k - 1]);
		}
	}
}

int getRMQ(int l, int r) {
	if (l > r) return 0;
	int len = lg2[r - l + 1]; // opt
	return max(rmq[l][len], rmq[r - (1 << len) + 1][len]);
}

int getLast(int l, int r) {
	auto itleft = lower_bound(query.begin(), query.end(), mp(l, -1LL));
	auto itRight = lower_bound(query.begin(), query.end(), mp(r, -1LL));
	return getRMQ(itleft - query.begin(), min(q, (int)(itRight - query.begin() - 1)));
}

void solve() {
	int ans = 0;
	int it = query.size() - 1;
	for (int i = 0; i < a.size(); i++) {
		while (it >= 1 && query[it].fi >= a[i].se) {
			update(query[it].se, 1);
			it--;
		}
		int last = getLast(a[i].fi, a[i].se);
		if (last) a[i].state = 1;
		last++;
		int rec = get(last);
		if (rec % 2) a[i].state ^= 1;
		if (a[i].state == 0) ans += a[i].fi;
		else ans += a[i].se;
	}
	cout << ans << endl;
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifdef in1code
	freopen("1test.inp", "r", stdin);
#endif
	for (int i = 1; i <= N - 5; i++) lg2[i] = log2(i);
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		int u, v; cin >> u >> v;
		if (u < v) a.push_back(data(u, v, 0));
		else a.push_back(data(v, u, 1));
	}
	sort(a.begin(), a.end(), cmp);
	query.push_back(mp(-1, -1));
	for (int i = 0; i < q; i++) {
		int t; cin >> t;
		query.push_back(mp(t, i + 1));
	}
	sort(query.begin(), query.end());
	initRMQ();
	solve();
}

Compilation message

fortune_telling2.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<long long int>&)':
fortune_telling2.cpp:24:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < x.size(); i++) os << x[i] << sp;
                    ^
fortune_telling2.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<std::pair<long long int, long long int> >&)':
fortune_telling2.cpp:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < x.size(); i++) os << x[i] << endl;
                    ^
fortune_telling2.cpp: In function 'void solve()':
fortune_telling2.cpp:85:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a.size(); i++) {
                    ^

Subtask #1
4.0 / 4.0

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 37508 KB Output is correct
2 Correct 29 ms 38404 KB Output is correct
3 Correct 43 ms 38404 KB Output is correct
4 Correct 53 ms 40196 KB Output is correct
5 Correct 73 ms 40196 KB Output is correct
6 Correct 56 ms 40196 KB Output is correct
7 Correct 56 ms 40196 KB Output is correct
8 Correct 53 ms 40196 KB Output is correct
9 Correct 39 ms 40196 KB Output is correct
10 Correct 46 ms 40196 KB Output is correct
11 Correct 43 ms 40196 KB Output is correct
12 Correct 39 ms 40196 KB Output is correct
13 Correct 33 ms 40196 KB Output is correct
14 Correct 46 ms 40196 KB Output is correct
15 Correct 39 ms 40196 KB Output is correct
16 Correct 56 ms 40196 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 43400 KB Output is correct
2 Correct 236 ms 45320 KB Output is correct
3 Correct 309 ms 47880 KB Output is correct
4 Correct 419 ms 50948 KB Output is correct
5 Correct 123 ms 42756 KB Output is correct
6 Correct 366 ms 50948 KB Output is correct
7 Correct 359 ms 50948 KB Output is correct
8 Correct 403 ms 50948 KB Output is correct
9 Correct 316 ms 50948 KB Output is correct
10 Correct 346 ms 50948 KB Output is correct
11 Correct 299 ms 50948 KB Output is correct
12 Correct 313 ms 50948 KB Output is correct
13 Correct 296 ms 50948 KB Output is correct
14 Correct 226 ms 50948 KB Output is correct
15 Correct 236 ms 50948 KB Output is correct
16 Correct 226 ms 50948 KB Output is correct
17 Correct 273 ms 50948 KB Output is correct
18 Correct 246 ms 50948 KB Output is correct
19 Correct 269 ms 50948 KB Output is correct
20 Correct 303 ms 50948 KB Output is correct