Submission #74043

#TimeUsernameProblemLanguageResultExecution timeMemory
74043kingpig9Fortune Telling 2 (JOI14_fortune_telling2)C++11
0 / 100
22 ms17016 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define debug(...) fprintf(stderr, __VA_ARGS__) //#define debug(...) #define fi first #define se second #define all(v) (v).begin(), (v).end() #define fillchar(a, s) memset((a), (s), sizeof(a)) const int MAXN = 1 << 20; struct segtree { int tr[2 * MAXN]; void init() { for (int i = 0; i < 2 * MAXN; i++) { tr[i] = -1e9; } } void update (int x, int v) { x += MAXN; tr[x] = v; while (x >>= 1) { tr[x] = max(tr[2 * x], tr[2 * x + 1]); } } int query (int a, int b, int cur = 1, int lt = 0, int rt = MAXN) { if (rt <= a || b <= lt) { return -1e9; } if (a <= lt && rt <= b) { return tr[cur]; } int mid = (lt + rt) / 2; return max(query(a, b, 2 * cur, lt, mid), query(a, b, 2 * cur + 1, mid, rt)); } }; int N, K; pii card[MAXN]; int T[MAXN]; vector<int> vals; segtree seg; int main() { scanf("%d %d", &N, &K); for (int i = 0; i < N; i++) { scanf("%d %d", &card[i].fi, &card[i].se); vals.push_back(card[i].fi); vals.push_back(card[i].se); } for (int i = 0; i < K; i++) { scanf("%d", &T[i]); vals.push_back(T[i]); } seg.init(); sort(all(vals)); vals.resize(unique(all(vals)) - vals.begin()); for (int i = 0; i < N; i++) { card[i].fi = lower_bound(all(vals), card[i].fi) - vals.begin(); card[i].se = lower_bound(all(vals), card[i].se) - vals.begin(); T[i] = lower_bound(all(vals), T[i]) - vals.begin(); } vector<pii> vt; for (int i = 0; i < K; i++) { seg.update(T[i], i); vt.push_back({T[i], i}); } sort(all(vt)); sort(card, card + N, [] (pii a, pii b) { return max(a.fi, a.se) > max(b.fi, b.se); }); oset<int> certain; //ones that are certainly going to flip the card ll ans = 0; for (int i = 0; i < N; i++) { int mnside = min(card[i].fi, card[i].se), mxside = max(card[i].fi, card[i].se); while (!vt.empty() && vt.back().fi >= mxside) { certain.insert(vt.back().se); vt.pop_back(); } int x = seg.query(mnside, mxside); //KEY IDEA: "maybe" is going to turn the card to the min. so certainly the last "maybe" will. bool flip = (certain.size() - certain.order_of_key(x)) % 2; int ind; if (x == -1e9) { ind = (flip ? card[i].se : card[i].fi); } else { ind = (flip ? mnside : mxside); } ans += vals[ind]; } printf("%lld\n", ans); }

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:60:7: 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:62:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &card[i].fi, &card[i].se);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:67:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &T[i]);
   ~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...