Submission #983716

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
983716	2024-05-16T01:41:50 Z	sare	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	756 ms	51220 KB

fortune_telling2

//In the name of Allah :)
#include <bits/stdc++.h>
using namespace std;
string to_string(char c) { return string(1,c); }
string to_string(bool b) { return b ? "true" : "false"; }
string to_string(const char* s) { return (string)s; }
string to_string(string s) { return s; }
string to_string(vector<bool> v) { 
	string res = "{"; for(int i = 0; i < (int)v.size(); i++) res += char('0'+v[i]);
	res += "}"; return res; }
template<size_t SZ> string to_string(bitset<SZ> b) {
	string res = ""; for(size_t i = 0; i < SZ; i++) res += char('0'+b[i]);
	return res; }
template<class A, class B> string to_string(pair<A,B> p);
template<class T> string to_string(T v) { // containers with begin(), end()
	bool fst = 1; string res = "{";
	for (const auto& x: v) {
		if (!fst) res += ", ";
		fst = 0; res += to_string(x);
	}
	res += "}"; return res;
}
template<class A, class B> string to_string(pair<A,B> p) {
	return "("+to_string(p.first)+", "+to_string(p.second)+")"; }
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
	cerr << to_string(h); if (sizeof...(t)) cerr << ", ";
	DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL
#define wis(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "] : [", DBG(__VA_ARGS__)
#else
#define wis(...) 0
#endif
typedef long long ll;
#define all(x) (x).begin(), (x).end()
const int MAXN = 2e5 + 10;
int n, k, a[MAXN], b[MAXN], t[MAXN];
vector<int> seg[MAXN << 2];

void build(int nd, int cl, int cr) {
	if (cr - cl == 1) {
		seg[nd] = {t[cl]};
		return;
	}
	int L = nd << 1, R = L | 1, mid = (cr + cl) >> 1;
	build(L, cl, mid);
	build(R, mid, cr);
	seg[nd].resize(seg[L].size() + seg[R].size());
	merge(seg[L].begin(), seg[L].end(), seg[R].begin(), seg[R].end(), seg[nd].begin());
}
inline void build() {
	build(1, 0, k);
}

int query(int nd, int cl, int cr, int ind, int val) {
	if (cl >= ind) {
		return seg[nd].end() - lower_bound(all(seg[nd]), val);
	}
	if (ind >= cr) {
		return 0;
	}
	int L = nd << 1, R = L | 1, mid = (cr + cl) >> 1, ret = 0;
	if (ind >= mid) {
		ret = query(R, mid, cr, ind, val);
	}
	else {
		ret = query(L, cl, mid, ind, val) + query(R, mid, cr, ind, val);
	}
	return ret;
}
inline int query(int ind, int val) { // return how many numbers after ind has value greater than or equal val
	int ret = query(1, 0, k, ind, val);
	return ret;
}

inline int last(int l, int r) { //[l, r]
	if (l > r) {
		return -1;
	}
	auto check = [&](int mid) {
		return query(mid, l) - query(mid, r + 1) > 0;
	};
	int bl = -1, br = k;
	while (br - bl > 1) {
		int mid = (bl + br) >> 1;
		if (check(mid)) {
			bl = mid;
		}
		else {
			br = mid;
		}
	}
	return bl;
}

int main() {
	ios::sync_with_stdio(0);
#ifndef LOCAL
	cin.tie(0);
#endif
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i];
	}
	for (int i = 0; i < k; i++) {
		cin >> t[i];
	}
	build();
	ll ans = 0;
	for (int i = 0; i < n; i++) {
		int lst = last(min(a[i], b[i]), max(a[i], b[i]) - 1);
		int cnt = query(lst + 1, max(a[i], b[i]));
		wis(a[i], b[i], lst, cnt);
		if (lst == -1) {
			if (cnt % 2 == 0) {
				wis(a[i]);
				ans += a[i];
			}
			else {
				wis(b[i]);
				ans += b[i];
			}
		}
		else {
			if (b[i] > a[i]) {
				swap(a[i], b[i]);
			}
			if (cnt % 2 == 0) {
				wis(a[i]);
				ans += a[i];
			}
			else {
				wis(b[i]);
				ans += b[i];
			}
		}
	}
	cout << ans << '\n';
}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:32:18: warning: statement has no effect [-Wunused-value]
   32 | #define wis(...) 0
      |                  ^
fortune_telling2.cpp:113:3: note: in expansion of macro 'wis'
  113 |   wis(a[i], b[i], lst, cnt);
      |   ^~~
fortune_telling2.cpp:32:18: warning: statement has no effect [-Wunused-value]
   32 | #define wis(...) 0
      |                  ^
fortune_telling2.cpp:116:5: note: in expansion of macro 'wis'
  116 |     wis(a[i]);
      |     ^~~
fortune_telling2.cpp:32:18: warning: statement has no effect [-Wunused-value]
   32 | #define wis(...) 0
      |                  ^
fortune_telling2.cpp:120:5: note: in expansion of macro 'wis'
  120 |     wis(b[i]);
      |     ^~~
fortune_telling2.cpp:32:18: warning: statement has no effect [-Wunused-value]
   32 | #define wis(...) 0
      |                  ^
fortune_telling2.cpp:129:5: note: in expansion of macro 'wis'
  129 |     wis(a[i]);
      |     ^~~
fortune_telling2.cpp:32:18: warning: statement has no effect [-Wunused-value]
   32 | #define wis(...) 0
      |                  ^
fortune_telling2.cpp:133:5: note: in expansion of macro 'wis'
  133 |     wis(b[i]);
      |     ^~~

Subtask #1

4.0 / 4.0

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

Subtask #2

31.0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	21080 KB	Output is correct
2	Correct	7 ms	21252 KB	Output is correct
3	Correct	6 ms	21080 KB	Output is correct
4	Correct	6 ms	21084 KB	Output is correct
5	Correct	6 ms	21084 KB	Output is correct
6	Correct	6 ms	21080 KB	Output is correct
7	Correct	7 ms	21084 KB	Output is correct
8	Correct	6 ms	21280 KB	Output is correct
9	Correct	6 ms	21084 KB	Output is correct
10	Correct	6 ms	21084 KB	Output is correct
11	Correct	6 ms	21084 KB	Output is correct
12	Correct	6 ms	21080 KB	Output is correct
13	Correct	7 ms	21280 KB	Output is correct
14	Correct	25 ms	22364 KB	Output is correct
15	Correct	50 ms	23644 KB	Output is correct
16	Correct	75 ms	25284 KB	Output is correct
17	Correct	105 ms	26696 KB	Output is correct
18	Correct	127 ms	26640 KB	Output is correct
19	Correct	101 ms	26712 KB	Output is correct
20	Correct	114 ms	26704 KB	Output is correct
21	Correct	90 ms	26676 KB	Output is correct
22	Correct	56 ms	26236 KB	Output is correct
23	Correct	54 ms	26200 KB	Output is correct
24	Correct	55 ms	26224 KB	Output is correct
25	Correct	54 ms	26256 KB	Output is correct
26	Correct	97 ms	26456 KB	Output is correct
27	Correct	184 ms	26716 KB	Output is correct
28	Correct	102 ms	26492 KB	Output is correct
29	Correct	285 ms	26700 KB	Output is correct

Subtask #3

65.0 / 65.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	21080 KB	Output is correct
2	Correct	7 ms	21252 KB	Output is correct
3	Correct	6 ms	21080 KB	Output is correct
4	Correct	6 ms	21084 KB	Output is correct
5	Correct	6 ms	21084 KB	Output is correct
6	Correct	6 ms	21080 KB	Output is correct
7	Correct	7 ms	21084 KB	Output is correct
8	Correct	6 ms	21280 KB	Output is correct
9	Correct	6 ms	21084 KB	Output is correct
10	Correct	6 ms	21084 KB	Output is correct
11	Correct	6 ms	21084 KB	Output is correct
12	Correct	6 ms	21080 KB	Output is correct
13	Correct	7 ms	21280 KB	Output is correct
14	Correct	25 ms	22364 KB	Output is correct
15	Correct	50 ms	23644 KB	Output is correct
16	Correct	75 ms	25284 KB	Output is correct
17	Correct	105 ms	26696 KB	Output is correct
18	Correct	127 ms	26640 KB	Output is correct
19	Correct	101 ms	26712 KB	Output is correct
20	Correct	114 ms	26704 KB	Output is correct
21	Correct	90 ms	26676 KB	Output is correct
22	Correct	56 ms	26236 KB	Output is correct
23	Correct	54 ms	26200 KB	Output is correct
24	Correct	55 ms	26224 KB	Output is correct
25	Correct	54 ms	26256 KB	Output is correct
26	Correct	97 ms	26456 KB	Output is correct
27	Correct	184 ms	26716 KB	Output is correct
28	Correct	102 ms	26492 KB	Output is correct
29	Correct	285 ms	26700 KB	Output is correct
30	Correct	108 ms	46832 KB	Output is correct
31	Correct	217 ms	47636 KB	Output is correct
32	Correct	369 ms	48980 KB	Output is correct
33	Correct	645 ms	50980 KB	Output is correct
34	Correct	70 ms	46672 KB	Output is correct
35	Correct	671 ms	51156 KB	Output is correct
36	Correct	646 ms	51160 KB	Output is correct
37	Correct	686 ms	51152 KB	Output is correct
38	Correct	625 ms	51160 KB	Output is correct
39	Correct	677 ms	51088 KB	Output is correct
40	Correct	497 ms	50948 KB	Output is correct
41	Correct	624 ms	51024 KB	Output is correct
42	Correct	652 ms	51160 KB	Output is correct
43	Correct	267 ms	50260 KB	Output is correct
44	Correct	271 ms	50652 KB	Output is correct
45	Correct	277 ms	50260 KB	Output is correct
46	Correct	292 ms	49280 KB	Output is correct
47	Correct	454 ms	48980 KB	Output is correct
48	Correct	756 ms	51220 KB	Output is correct
49	Correct	694 ms	51080 KB	Output is correct