Submission #169487

#TimeUsernameProblemLanguageResultExecution timeMemory
169487tcm운세 보기 2 (JOI14_fortune_telling2)C++14
100 / 100
1236 ms55844 KiB
#include <bits/stdc++.h> #define fname "FORTELL2" #define bug(x) cerr << (#x) << " = " << (x) << '\n' #define ll long long #define ld long double #define ull unsigned long long #define ui unsigned int #define REP0(i, n) for(int i = 0, _n = (n); i < _n; ++i) #define REP1(i, n) for(int i = 1, _n = (n); i <= _n; ++i) #define REPB0(i, n) for(int i = (n) - 1; i >= 0; --i) #define REPB1(i, n) for(int i = (n); i > 0; --i) #define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i) #define FORB(i, a, b) for(int i = (a), _b = (b); i >= _b; --i) #define ARR0(a, n) {cerr <<(#a)<< ": ["; REP0(i, n) cerr<< ' ' << a[i] <<','; cerr<<"]\n";} #define ARR1(a, n) {cerr <<(#a)<< ": ["; REP1(i, n) cerr<< ' ' << a[i] <<','; cerr<<"]\n";} #define pb push_back #define pf push_front #define popb pop_back #define popf pop_front #define ins insert #define ers erase #define LB lower_bound #define UB upper_bound #define X first #define Y second using namespace std; template<typename T, typename V> inline void bugp(const pair<T, V> &x) {cerr << '{' << x.X << ", " << x.Y << "}\n";} template<typename T, typename U, typename V> inline void bugpp(const pair<T, pair<U, V> > &x) {cerr << '{' << x.X << ", {" << x.Y.X << ", " << x.Y.Y << "}}\n";} typedef pair<int, int> ii; typedef pair<ll, ll> pll; typedef pair<float, float> ff; typedef pair<int, ii> iii; typedef pair<ll, int> li; typedef pair<int, ll> il; typedef pair<ll, ii> lii; const int N = 200002, K = 200002; int n, k, sz, H[N+N+K], arr[N+N+K], Max[N+N+K << 2], ans[N], ind[K], fen[N+N+K]; ii coin[N]; struct Query { int C, id; bool operator <(const Query &qq) const {return C > qq.C;} } Q[K]; struct Que { int val, L, R, id; bool operator <(const Que &qq) const {return val > qq.val;} } data[N]; inline bool cmp(const Query &q1, const Query &q2) {return q1.id < q2.id;} void compress() { set<int> s; REP1(i, n) { s.ins(coin[i].X); s.ins(coin[i].Y); } REP1(i, k) s.ins(Q[i].C); vector<int> tmp(s.begin(), s.end()); int temp; REP1(i, n) { temp = LB(tmp.begin(), tmp.end(), coin[i].X) - tmp.begin() + 1; H[temp] = coin[i].X; coin[i].X = temp; temp = LB(tmp.begin(), tmp.end(), coin[i].Y) - tmp.begin() + 1; H[temp] = coin[i].Y; coin[i].Y = temp; } REP1(i, k) { Q[i].C = LB(tmp.begin(), tmp.end(), Q[i].C) - tmp.begin() + 1; arr[Q[i].C] = i; } sz = tmp.size(); } void build(int x = 1, int l = 1, int r = sz) { if(l == r) Max[x] = arr[l]; else { int mid = (l + r) >> 1; build(x << 1, l, mid); build(x << 1 | 1, mid + 1, r); Max[x] = max(Max[x << 1], Max[x << 1 | 1]); } } int getMax(int u, int v, int x = 1, int l = 1, int r = sz) { if(u > r || v < l) return INT_MIN; else if(u <= l && r <= v) return Max[x]; int mid = (l + r) >> 1; return max(getMax(u, v, x << 1, l, mid), getMax(u, v, x << 1 | 1, mid + 1, r)); } void update(int i) {for(; i <= sz; i += i&-i) ++fen[i];} int getSum(int u, int v) { int fi = 0, se = 0; --u; for(; u; u &= u - 1) fi += fen[u]; for(; v; v &= v - 1) se += fen[v]; return se - fi; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); scanf("%d %d", &n, &k); REP1(i, n) scanf("%d %d", &coin[i].X, &coin[i].Y); REP1(i, k) { scanf("%d", &Q[i].C); Q[i].id = i; } compress(); build(); int pos, x, y, cnt = 0; REP1(i, n) { if(coin[i].X == coin[i].Y) ans[i] = H[coin[i].X]; else { x = min(coin[i].X, coin[i].Y); y = max(coin[i].X, coin[i].Y); pos = getMax(x, y - 1); if(pos == k) ans[i] = H[y]; else if(!pos) data[++cnt] = {coin[i].X, pos + 1, k, i}; else data[++cnt] = {y, pos + 1, k, i}; } } sort(data + 1, data + cnt + 1); sort(Q + 1, Q + k + 1); REP1(i, k) ind[i] = Q[i].id; sort(Q + 1, Q + k + 1, cmp); int j = 1, res; REP1(i, cnt) { while(Q[ind[j]].C >= data[i].val && j <= k) update(ind[j++]); res = getSum(data[i].L, data[i].R); if(res&1) { if(data[i].val == coin[data[i].id].X) ans[data[i].id] = H[coin[data[i].id].Y]; else ans[data[i].id] = H[coin[data[i].id].X]; } else ans[data[i].id] = H[data[i].val]; } ll sum = 0; REP1(i, n) sum += ans[i]; cout << sum; return 0; }

Compilation message (stderr)

fortune_telling2.cpp:40:44: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
 int n, k, sz, H[N+N+K], arr[N+N+K], Max[N+N+K << 2], ans[N], ind[K], fen[N+N+K];
                                         ~~~^~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:106:10: 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:107:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     REP1(i, n) scanf("%d %d", &coin[i].X, &coin[i].Y);
                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:109:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &Q[i].C);
         ~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...