#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#include <sstream>
#include <iterator>
#include <numeric>
using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
class Mapping
{
public:
void init(const vector<int>& raw, int base = 0)
{
start = base;
arr = raw;
sort(arr.begin(), arr.end());
arr.erase(unique(arr.begin(), arr.end()), arr.end());
for (int i = 0; i < arr.size(); i++)
idx[arr[i]] = base + i;
}
int get_idx(int k)
{
return idx[k];
}
int get_value(int idx)
{
return arr[idx - start];
}
private:
int start;
vector<int> arr;
map<int, int> idx;
};
template<typename T>
class SegmentTree
{
public:
void init(vector<T>& raw)
{
assert(!is_init);
is_init = true;
n = raw.size();
int h = (int)ceil(log2(n));
int tree_size = (1 << (h + 1));
data.resize(tree_size);
value = raw;
init_internal(raw, 1, 0, n - 1);
}
T add(int idx, const T& added)
{
assert(is_init);
return update(idx, value[idx] + added);
}
T update(int idx, const T& newVal)
{
assert(is_init);
return update_internal(1, 0, n - 1, idx, newVal);
}
T query(int left, int right)
{
assert(is_init);
return query_internal(1, 0, n - 1, left, right);
}
virtual T merge(const T& left, const T& right) = 0;
virtual T merge_with_idx(const T& left, const T& right, int left_idx, int right_idx)
{
return merge(left, right);
}
private:
vector<T> data;
vector<T> value;
int n;
bool is_init = false;
T init_internal(vector<T>& raw, int node, int start, int end)
{
int mid = (start + end) / 2;
if (start == end)
return data[node] = raw[start];
else
return data[node] = merge_with_idx(init_internal(raw, node * 2, start, mid),
init_internal(raw, node * 2 + 1, mid + 1, end), node * 2, node * 2 + 1);
}
T update_internal(int node, int start, int end, int index, const T& newVal)
{
if (index < start || index > end)
return data[node];
if (start == end)
{
data[node] = newVal;
value[index] = newVal;
}
else
{
int mid = (start + end) / 2;
data[node] = merge_with_idx(update_internal(node * 2, start, mid, index, newVal),
update_internal(node * 2 + 1, mid + 1, end, index, newVal), node * 2, node * 2 + 1);
}
return data[node];
}
T query_internal(int node, int start, int end, int left, int right)
{
if (left <= start && end <= right)
return data[node];
int mid = (start + end) / 2;
if (mid < left)
return query_internal(node * 2 + 1, mid + 1, end, left, right);
if (mid + 1 > right)
return query_internal(node * 2, start, mid, left, right);
return merge_with_idx(query_internal(node * 2, start, mid, left, right),
query_internal(node * 2 + 1, mid + 1, end, left, right), node * 2, node * 2 + 1);
}
};
class MaxTree : public SegmentTree<int>
{
public:
virtual int merge(const int& l, const int& r) override
{
return max(l, r);
}
};
class SumTree : public SegmentTree<int>
{
public:
virtual int merge(const int& l, const int& r) override
{
return l + r;
}
};
int card[200005][2];
int view[200005];
int main()
{
int n, k;
scanf("%d %d", &n, &k);
vector<int> numbers;
Mapping mapping;
for (int i = 0; i < n; i++)
{
scanf("%d %d", &card[i][0], &card[i][1]);
if (card[i][0] > card[i][1])
swap(card[i][0], card[i][1]);
numbers.push_back(card[i][0]);
numbers.push_back(card[i][1]);
}
vector<int> raw(numbers.size() + 5, 0);
SumTree sumTree;
MaxTree maxTree;
sumTree.init(raw);
maxTree.init(raw);
vector<int> q;
for (int i = 0; i < k; i++)
{
int t;
scanf("%d", &t);
q.push_back(t);
numbers.push_back(t);
}
mapping.init(numbers);
for (int i = 0; i < k; i++)
{
maxTree.update(mapping.get_idx(q[i]), i);
sumTree.add(mapping.get_idx(q[i]), 1);
}
vector<ii> ts;
for (int i = 0; i < n; i++)
{
int l = mapping.get_idx(card[i][0]);
int r = mapping.get_idx(card[i][1]) - 1;
auto s = 0;
if (l < r)
s = maxTree.query(l, r);
ts.emplace_back(s, i);
}
sort(ts.begin(), ts.end());
int qx = 0;
for (auto& ti : ts)
{
while (qx <= ti.first)
{
sumTree.add(mapping.get_idx(q[qx]), -1);
qx++;
}
int swapNum = sumTree.query(mapping.get_idx(card[ti.second][1]), numbers.size() + 1);
view[ti.second] = (swapNum + 1) % 2;
}
i64 ans = 0;
for (int i = 0; i < n; i++)
ans += card[i][view[i]];
printf("%lld\n", ans);
return 0;
}
Compilation message
fortune_telling2.cpp: In member function 'void Mapping::init(const std::vector<int>&, int)':
fortune_telling2.cpp:37:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < arr.size(); i++)
~~^~~~~~~~~~~~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:177: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:184:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &card[i][0], &card[i][1]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:206:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &t);
~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3135 ms |
393216 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3135 ms |
393216 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3135 ms |
393216 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
