Submission #119430

#TimeUsernameProblemLanguageResultExecution timeMemory
119430IOrtroiiiFortune Telling 2 (JOI14_fortune_telling2)C++14
35 / 100
92 ms22940 KiB
#include <bits/stdc++.h> using namespace std; const int N = 200200; int n, q; int x[N], y[N], z[N]; bool sw[N]; bool ft[N]; vector<pair<int, int>> vals; int rmq[18][N]; vector<pair<int, int>> qs[N]; void mdf(int v) { for (; v > 0; v -= v & -v) { ft[v] ^= true; } } bool get(int v) { bool ans = false; for (; v <= q; v += v & -v) { ans ^= ft[v]; } return ans; } int get(int l, int r) { int LG = __lg(r - l + 1); return max(rmq[LG][l], rmq[LG][r - (1 << LG) + 1]); } int main() { scanf("%d %d", &n, &q); for (int i = 1; i <= n; ++i) { scanf("%d %d", x + i, y + i); } for (int i = 1; i <= q; ++i) { scanf("%d", z + i); vals.emplace_back(z[i], i); } sort(vals.begin(), vals.end()); for (int i = 0; i < q; ++i) { rmq[0][i + 1] = vals[i].second; } for (int i = 1; i < 17; ++i) { for (int j = 1; j + (1 << i) - 1 <= q; ++j) { rmq[i][j] = max(rmq[i - 1][j], rmq[i - 1][j + (1 << i - 1)]); } } for (int i = 1; i <= n; ++i) { int l = min(x[i], y[i]), r = max(x[i], y[i]); l = lower_bound(vals.begin(), vals.end(), make_pair(l, 0)) - vals.begin() + 1; r = lower_bound(vals.begin(), vals.end(), make_pair(r, 0)) - vals.begin(); int last = 0; if (l <= r) { last = get(l, r); if (x[i] < y[i]) { swap(x[i], y[i]); } } qs[r].emplace_back(i, last + 1); } for (int i = q - 1; i >= 0; --i) { mdf(vals[i].second); for (auto v : qs[i]) { sw[v.first] = get(v.second); } } long long ans = 0; for (int i = 1; i <= n; ++i) { if (sw[i]) { ans += y[i]; } else { ans += x[i]; } } printf("%lld\n", ans); }

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:49:64: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
          rmq[i][j] = max(rmq[i - 1][j], rmq[i - 1][j + (1 << i - 1)]);
                                                              ~~^~~
fortune_telling2.cpp:35:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &n, &q);
    ~~~~~^~~~~~~~~~~~~~~~~
fortune_telling2.cpp:37:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d", x + i, y + i);
       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:40:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", z + i);
       ~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...