// BEGIN BOILERPLATE CODE
#include <bits/stdc++.h>
using namespace std;
#ifdef KAMIRULEZ
const bool kami_loc = true;
const long long kami_seed = 69420;
#else
const bool kami_loc = false;
const long long kami_seed = chrono::steady_clock::now().time_since_epoch().count();
#endif
const string kami_fi = "kamirulez.inp";
const string kami_fo = "kamirulez.out";
mt19937_64 kami_gen(kami_seed);
long long rand_range(long long rmin, long long rmax) {
uniform_int_distribution<long long> rdist(rmin, rmax);
return rdist(kami_gen);
}
void file_io(string fi, string fo) {
if (fi != "" && (!kami_loc || fi == kami_fi)) {
freopen(fi.c_str(), "r", stdin);
}
if (fo != "" && (!kami_loc || fo == kami_fo)) {
freopen(fo.c_str(), "w", stdout);
}
}
void set_up() {
if (kami_loc) {
file_io(kami_fi, kami_fo);
}
ios_base::sync_with_stdio(0);
cin.tie(0);
}
void just_do_it();
void just_exec_it() {
if (kami_loc) {
auto pstart = chrono::steady_clock::now();
just_do_it();
auto pend = chrono::steady_clock::now();
long long ptime = chrono::duration_cast<chrono::milliseconds>(pend - pstart).count();
string bar(50, '=');
cout << '\n' << bar << '\n';
cout << "Time: " << ptime << " ms" << '\n';
}
else {
just_do_it();
}
}
int main() {
set_up();
just_exec_it();
return 0;
}
// END BOILERPLATE CODE
// BEGIN MAIN CODE
const int ms = 2e5 + 20;
pair<int, int> a[ms];
pair<int, int> b[ms];
int f[ms];
int qs[ms];
int ma[ms];
int bit[ms * 4];
void update1(int px, int pp) {
for (int i = px; i < ms * 4; i += i & (-i)) {
bit[i] = max(bit[i], pp);
}
}
int get1(int px) {
int res = 0;
for (int i = px; i > 0; i -= i & (-i)) {
res = max(res, bit[i]);
}
return res;
}
void update2(int px) {
for (int i = px; i < ms * 4; i += i & (-i)) {
bit[i]++;
}
}
int get2(int px) {
int res = 0;
for (int i = px; i > 0; i -= i & (-i)) {
res += bit[i];
}
return res;
}
void just_do_it() {
int n, q;
cin >> n >> q;
vector<pair<int, pair<int, int>>> p;
for (int i = 1; i <= n; i++) {
cin >> a[i].first >> a[i].second;
if (a[i].first <= a[i].second) {
f[i] = 0;
}
else {
swap(a[i].first, a[i].second);
f[i] = 1;
}
b[i] = a[i];
p.push_back({a[i].first, {i, 1}});
p.push_back({a[i].second - 1, {i, -1}});
p.push_back({a[i].second, {i, 2}});
}
for (int i = 1; i <= q; i++) {
cin >> qs[i];
p.push_back({qs[i], {i, 3}});
}
sort(p.begin(), p.end());
int cc = 1;
int sz = p.size();
for (int i = 0; i < sz; i++) {
if (p[i].second.second == 1) {
a[p[i].second.first].first = cc;
}
if (p[i].second.second == 2) {
a[p[i].second.first].second = cc;
}
if (p[i].second.second == 3) {
qs[p[i].second.first] = cc;
}
if (i < sz - 1 && p[i].first != p[i + 1].first) {
cc++;
}
}
p.clear();
for (int i = 1; i <= n; i++) {
p.push_back({a[i].first, {1, i}});
}
for (int i = 1; i <= q; i++) {
p.push_back({qs[i], {2, i}});
}
sort(p.begin(), p.end(), greater<pair<int, pair<int, int>>>());
for (auto x: p) {
if (x.second.first == 2) {
update1(x.first, x.second.second);
}
else {
ma[x.second.second] = get1(a[x.second.second].second - 1);
}
}
for (int i = 1; i <= n; i++) {
if (ma[i] > 0) {
f[i] = 1;
}
}
fill_n(bit, ms * 4, 0);
p.clear();
for (int i = 1; i <= n; i++) {
p.push_back({a[i].second, {1, i}});
}
for (int i = 1; i <= q; i++) {
p.push_back({qs[i], {2, i}});
}
sort(p.begin(), p.end(), greater<pair<int, pair<int, int>>>());
cc = 0;
for (auto x: p) {
if (x.second.first == 2) {
update2(x.second.second);
cc++;
}
else {
f[x.second.second] += cc - get1(ma[x.second.second]);
f[x.second.second] %= 2;
}
}
long long res = 0;
for (int i = 1; i <= n; i++) {
if (f[i] == 0) {
res += b[i].first;
}
else {
res += b[i].second;
}
}
cout << res;
}
// END MAIN CODE
Compilation message
fortune_telling2.cpp: In function 'void file_io(std::string, std::string)':
fortune_telling2.cpp:25:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
25 | freopen(fi.c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:28:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
28 | freopen(fo.c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
