Submission #1174140

#TimeUsernameProblemLanguageResultExecution timeMemory
1174140chikien2009Fortune Telling 2 (JOI14_fortune_telling2)C++20
0 / 100
165 ms327680 KiB
#include <bits/stdc++.h> using namespace std; void setup() { #ifndef ONLINE_JUDGE freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout); #endif ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); } class SEGMENT_TREE { private: int tree_size; vector<vector<int>> tree; vector<int> base; inline void Build(int ind, int l, int r) { if (l == r) { tree[ind] = {base[l]}; return; } int m = (l + r) >> 1; Build(ind << 1, l, m); Build(ind << 1 | 1, m + 1, r); tree[ind].resize(r - l + 1); merge(tree[ind << 1].begin(), tree[ind << 1].end(), tree[ind << 1 | 1].begin(), tree[ind << 1 | 1].end(), tree[ind].begin()); } inline pair<int, int> Get(int ind, int l, int r, int x, int y) { int a = lower_bound(tree[ind].begin(), tree[ind].end(), x) - tree[ind].begin(); int b = lower_bound(tree[ind].begin(), tree[ind].end(), y) - tree[ind].begin(); if (a == b) { return {0, tree[ind].size() - b}; } if (l == r) { return {1, 0}; } int m = (l + r) >> 1; pair<int, int> rt = Get(ind << 1 | 1, m + 1, r, x, y); if (rt.first) { return rt; } pair<int, int> lt = Get(ind << 1, l, m, x, y); return make_pair(lt.first, lt.second ^ rt.second); } public: inline void Init(vector<int> inp) { base = inp; tree_size = inp.size(); tree.clear(); tree.resize(tree_size << 2); base.insert(base.begin(), 0); Build(1, 1, tree_size); } inline pair<int, int> Get(int x, int y) { return Get(1, 1, tree_size, x, y); } } st; int n, k, a[200000], b[200000]; vector<int> t; pair<int, int> r; long long res = 0; int main() { setup(); cin >> n >> k; t.resize(k); for (int i = 0; i < n; ++i) { cin >> a[i] >> b[i]; } for (int i = 0; i < k; ++i) { cin >> t[i]; } st.Init(t); r = st.Get(1, 9); for (int i = 0; i < n; ++i) { r = st.Get(min(a[i], b[i]), max(a[i], b[i])); if (r.first && a[i] < b[i]) { swap(a[i], b[i]); } res += (r.second & 1 ? b[i] : a[i]); } cout << res; return 0; }

Compilation message (stderr)

fortune_telling2.cpp: In function 'void setup()':
fortune_telling2.cpp:8:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |     freopen("test.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:9:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |     freopen("test.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...