Submission #983716

#	Time	Username	Problem	Language	Result	Execution time	Memory
983716		sare	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	756 ms	51220 KiB

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 (stderr)

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 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65