Submission #1174141

#TimeUsernameProblemLanguageResultExecution timeMemory
1174141chikien2009운세 보기 2 (JOI14_fortune_telling2)C++20
100 / 100
485 ms46904 KiB
#include <bits/stdc++.h> using namespace std; void setup() { 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...