oj.uz

답안 #983716

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
983716 2024-05-16T01:41:50 Z sare 운세 보기 2 (JOI14_fortune_telling2) C++17
100 / 100
 756 ms 51220 KB 
//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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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