#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[20] = {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[200000];
vii qs;
int rmqtbl[200000][18];
int rminqtbl[200000][18];
vii tickets;
bool kucuk[200000];
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)log2(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)log2(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);
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++) {
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;
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]);
}
int lim = max(cisimler[x].first, cisimler[x].second);
int a = bitget(524286) - 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 |
33480 KB |
Output is correct |
| 2 |
Correct |
0 ms |
33480 KB |
Output is correct |
| 3 |
Correct |
3 ms |
33612 KB |
Output is correct |
| 4 |
Correct |
0 ms |
33612 KB |
Output is correct |
| 5 |
Correct |
3 ms |
33612 KB |
Output is correct |
| 6 |
Correct |
3 ms |
33612 KB |
Output is correct |
| 7 |
Correct |
3 ms |
33612 KB |
Output is correct |
| 8 |
Correct |
3 ms |
33612 KB |
Output is correct |
| 9 |
Correct |
3 ms |
33612 KB |
Output is correct |
| 10 |
Correct |
0 ms |
33480 KB |
Output is correct |
| 11 |
Correct |
3 ms |
33480 KB |
Output is correct |
| 12 |
Correct |
3 ms |
33480 KB |
Output is correct |
| 13 |
Correct |
3 ms |
33480 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
53 ms |
36584 KB |
Output is correct |
| 2 |
Correct |
106 ms |
39912 KB |
Output is correct |
| 3 |
Correct |
219 ms |
42724 KB |
Output is correct |
| 4 |
Correct |
346 ms |
46692 KB |
Output is correct |
| 5 |
Correct |
369 ms |
46692 KB |
Output is correct |
| 6 |
Correct |
316 ms |
46692 KB |
Output is correct |
| 7 |
Correct |
336 ms |
46692 KB |
Output is correct |
| 8 |
Correct |
276 ms |
46688 KB |
Output is correct |
| 9 |
Correct |
186 ms |
42940 KB |
Output is correct |
| 10 |
Correct |
126 ms |
41064 KB |
Output is correct |
| 11 |
Correct |
129 ms |
39660 KB |
Output is correct |
| 12 |
Correct |
169 ms |
44012 KB |
Output is correct |
| 13 |
Correct |
196 ms |
42316 KB |
Output is correct |
| 14 |
Correct |
243 ms |
42948 KB |
Output is correct |
| 15 |
Correct |
213 ms |
42940 KB |
Output is correct |
| 16 |
Correct |
279 ms |
44812 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
676 ms |
56132 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
