Submission #56741

#TimeUsernameProblemLanguageResultExecution timeMemory
56741ruhanhabib39Fortune Telling 2 (JOI14_fortune_telling2)C++17
0 / 100
4 ms616 KiB
#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); } int mx[4 * MAXN + 10]; void mx_upd(int cn, int b, int e, int i, int x) { if(i < b || i > e) return; if(b == e) { mx[cn] = x; return; } int m = (b + e) / 2; mx_upd(cn << 1, b, m, i, x); mx_upd(cn << 1 | 1, m+1, e, i, x); mx[cn] = max(mx[cn << 1], mx[cn << 1 | 1]); } int nxt(int cn, int b, int e, int x) { if(mx[cn] < x) return -1; if(b == e) return b; int m = (b + e) / 2; if(mx[cn<<1|1] < x) return nxt(cn << 1, b, m, x); return nxt(cn << 1 | 1, m+1, e, x); } int solve(int i) { int l = nxt(1, 0, K-1, min(A[i].first, A[i].second)); 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); 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 mx_upd(1, 0, K-1, i, X[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); 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; mx_upd(1, 0, K-1, j, -1); inc(j); st.erase(*st.rbegin()); } res += solve(i); } printf("%lld\n", res); }

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:65:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &N, &K);
    ~~~~~^~~~~~~~~~~~~~~~
fortune_telling2.cpp:67:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d%d", &A[i].first, &A[i].second);
       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:70:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &X[i]);
       ~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...