# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
56696 | ruhanhabib39 | Fortune Telling 2 (JOI14_fortune_telling2) | C++17 | 3 ms | 376 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5;
int N, K;
pair<int,int> A[MAXN + 10];
int bit[MAXN + 10];
int X[MAXN + 10];
set<int> spos;
void inc(int i) {
for(i++; i <= K; i += i & (-i)) {
bit[i] ^= 1;
}
}
int sum(int r) {
int res = 0;
for(r++; r > 0; r -= r & (-r)) {
res ^= bit[r];
}
return res;
}
int sum(int l, int r) {
return sum(r) ^ sum(l-1);
}
int solve(int i) {
int l = *spos.rbegin();
int p = sum(l, K-1);
if(l != -1) {
if(A[i].first < A[i].second) swap(A[i].first, A[i].second);
}
if(p) return A[i].second;
else return A[i].first;
}
int main() {
scanf("%d%d", &N, &K);
for(int i = 0; i < N; i++) {
scanf("%d%d", &A[i].first, &A[i].second);
}
for(int i = 0; i < K; i++) {
scanf("%d", &X[i]);
}
sort(A, A + N,
[](pair<int,int> a, pair<int,int> b) {
int ma = max(a.first, a.second);
int mb = max(b.first, b.second);
if(ma != mb) return ma < mb;
return a < b;
});
reverse(A, A + N);
spos.insert(-1);
for(int i = 0; i < K; i++) {
if(X[i] < min(A[0].first, A[0].second)) continue;
if(X[i] < max(A[0].first, A[0].second)) { // S
spos.insert(i);
}
}
set<pair<long long,int>> st;
for(int i = 0; i < K; i++) {
st.emplace(X[i], i);
}
while(st.size() && st.rbegin()->first >= max(A[0].first, A[0].second)) {
inc(st.rbegin()->second);
st.erase(*st.rbegin());
}
long long res = solve(0);
int a = min(A[0].first, A[0].second), b = max(A[0].first, A[0].second);
for(int i = 1; i < N; i++) {
while(st.size() && st.rbegin()->first >= max(A[i].first, A[i].second)) {
int j = st.rbegin()->second;
spos.erase(j);
inc(j);
st.erase(*st.rbegin());
}
res += solve(i);
}
printf("%lld\n", res);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |