#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<pair<int, int> > vii;
typedef vector<vector<pair<int, int> > > vvii;
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)
int twopow[22] = {0};
// x is always 2
int mypow(int x, int e) {
if (twopow[e]) return twopow[e];
if (e == 0) return 1;
int a = mypow(x, e/2);
return (twopow[e] = (e % 2 == 0) ? a*a : a*a*x);
}
int N, K;
vii cisimler;
map<int, int> tbl;
map<int, int> revtbl;
int queries[200002];
vii qs;
int rmqtbl[200002][19];
int rminqtbl[200002][19];
vii tickets;
bool kucuk[200002];
int lg2[270000];
int rmq(int a, int b) {
//cerr << "max of: ";
//for (int i = a; i <= b; i++) {
//cerr << rmqtbl[i][0] << " ";
//}
int pop = b - a + 1;
int e = (int)lg2[pop];
int a2 = b - mypow(2, e) + 1;
return max(rmqtbl[a][e], rmqtbl[a2][e]);
}
int rminq(int a, int b) {
int pop = b - a + 1;
int e = (int)lg2[pop];
int a2 = b - mypow(2, e) + 1;
return min(rminqtbl[a][e], rminqtbl[a2][e]);
}
int binsrc(int x) {
int l = 0, r = K;
while (r > l) {
int mid = (l + r) / 2;
if (qs[mid].first >= x) r = mid;
else l = mid+1;
}
return l;
}
int bit[524289] = {0};
void bitinc(int x) {
x += 2;
while (x <= 524288) {
bit[x]++;
x += x & -x;
}
}
int bitget(int x) {
x += 2;
int sum = 0;
while (x > 0) {
sum += bit[x];
x -= x & -x;
}
return sum;
}
int main(int argc, char **argv) {
//freopen("input", "r", stdin);
//freopen("output", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
int lgcur = 1;
for (int i = 1; i < 19; i++) {
int lim = mypow(2, i);
for ( ; lgcur < lim; lgcur++) {
lg2[lgcur] = i-1;
}
}
cin >> N >> K;
set<int> S;
for (int i = 0; i < N; i++) {
int a, b; cin >> a >> b;
cisimler.pb(mp(a, b));
S.insert(a);
S.insert(b);
}
for (int i = 0; i < K; i++) {
int a; cin >> a;
queries[i] = a;
qs.pb(mp(a, i));
S.insert(a);
}
int c = 0;
while ( ! S.empty() ) {
int x = *S.begin();
S.erase(S.begin());
tbl[x] = c;
revtbl[c] = x;
c++;
}
for (int i = 0; i < N; i++) {
cisimler[i].first = tbl[cisimler[i].first];
cisimler[i].second = tbl[cisimler[i].second];
//cerr << i << " " << revtbl[cisimler[i].first] << " " << revtbl[cisimler[i].second] << "\n";
}
for (int i = 0; i < K; i++) {
queries[i] = tbl[queries[i]];
qs[i].first = tbl[qs[i].first];
}
sort(qs.begin(), qs.end());
for (int i = 0; i < K; i++) {
rmqtbl[i][0] = qs[i].second;
rminqtbl[i][0] = qs[i].second;
}
for (int e = 1; e < 18; e++) {
int off = mypow(2, e-1);
for (int i = 0; i < K; i++) {
if (i+2*off > K) break;
rmqtbl[i][e] = max(rmqtbl[i][e-1], rmqtbl[i+off][e-1]);
rminqtbl[i][e] = min(rminqtbl[i][e-1], rminqtbl[i+off][e-1]);
}
}
for (int i = 0; i < N; i++) {
int cmin = min(cisimler[i].first, cisimler[i].second);
int cmax = max(cisimler[i].first, cisimler[i].second);
int ls = binsrc(cmin);
//cerr << cmin << endl;
int hs = binsrc(cmax);
if (ls == K) {
kucuk[i] = (cmin == cisimler[i].first);
continue;
}
if (hs == K) {
kucuk[i] = false;
continue;
}
//cerr << "ls : " << ls << " hs : " << hs << endl;
if (ls != hs) {
int q = rmq(ls, hs-1);
//cerr << " is " << q << endl;
tickets.pb(mp(q+1, i));
}
else {
int q = rminq(ls, K-1);
//cerr << ls << " " << q << endl;
if (cmin == cisimler[i].first) {
tickets.pb(mp(q+1, i));
}
else {
tickets.pb(mp(q, i));
}
}
}
/*for (int i = 0; i < tickets.size(); i++) {
cerr << tickets[i].first << " " << tickets[i].second << endl;
}*/
int cur = K;
int tot = 0;
sort(tickets.begin(), tickets.end());
for (int i = tickets.size()-1; i >= 0; i--) {
int x = tickets[i].second;
while (cur > tickets[i].first) {
cur--;
bitinc(queries[cur]);
tot++;
}
int lim = max(cisimler[x].first, cisimler[x].second);
int a = tot - bitget(lim-1);
//if (x == 3) cerr << lim << "\n";
kucuk[x] = (a % 2 == 1);
}
ll sum = 0;
for (int i = 0; i < N; i++) {
//cerr << kucuk[i] << endl;
if (kucuk[i]) {
sum += revtbl[ min(cisimler[i].first, cisimler[i].second) ];
}
else {
sum += revtbl[ max(cisimler[i].first, cisimler[i].second) ];
}
}
cout << sum << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
36088 KB |
Output is correct |
| 2 |
Correct |
0 ms |
36088 KB |
Output is correct |
| 3 |
Correct |
3 ms |
36220 KB |
Output is correct |
| 4 |
Correct |
3 ms |
36220 KB |
Output is correct |
| 5 |
Correct |
3 ms |
36220 KB |
Output is correct |
| 6 |
Correct |
3 ms |
36220 KB |
Output is correct |
| 7 |
Correct |
3 ms |
36220 KB |
Output is correct |
| 8 |
Correct |
0 ms |
36220 KB |
Output is correct |
| 9 |
Correct |
3 ms |
36220 KB |
Output is correct |
| 10 |
Correct |
3 ms |
36088 KB |
Output is correct |
| 11 |
Correct |
0 ms |
36088 KB |
Output is correct |
| 12 |
Correct |
3 ms |
36088 KB |
Output is correct |
| 13 |
Correct |
0 ms |
36088 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
53 ms |
39192 KB |
Output is correct |
| 2 |
Correct |
123 ms |
42520 KB |
Output is correct |
| 3 |
Correct |
246 ms |
45332 KB |
Output is correct |
| 4 |
Correct |
336 ms |
49300 KB |
Output is correct |
| 5 |
Correct |
289 ms |
49300 KB |
Output is correct |
| 6 |
Correct |
303 ms |
49300 KB |
Output is correct |
| 7 |
Correct |
296 ms |
49300 KB |
Output is correct |
| 8 |
Correct |
286 ms |
49296 KB |
Output is correct |
| 9 |
Correct |
169 ms |
45548 KB |
Output is correct |
| 10 |
Correct |
106 ms |
43672 KB |
Output is correct |
| 11 |
Correct |
123 ms |
42268 KB |
Output is correct |
| 12 |
Correct |
166 ms |
46620 KB |
Output is correct |
| 13 |
Correct |
149 ms |
44924 KB |
Output is correct |
| 14 |
Correct |
206 ms |
45556 KB |
Output is correct |
| 15 |
Correct |
179 ms |
45548 KB |
Output is correct |
| 16 |
Correct |
256 ms |
47420 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
639 ms |
58924 KB |
Output is correct |
| 2 |
Correct |
1153 ms |
67700 KB |
Output is correct |
| 3 |
Correct |
1656 ms |
78608 KB |
Output is correct |
| 4 |
Execution timed out |
2000 ms |
100428 KB |
Execution timed out |
| 5 |
Halted |
0 ms |
0 KB |
- |
