#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define maxn 220000
int n, q, tr[4*maxn], trs[4*maxn], a[maxn], b[maxn], t[maxn], ccval[5* maxn];
void att(int no, int l, int r, int pos, int val) {
if(l > pos || r < pos) return;
if(l == r) {
tr[no] = max(tr[no],val);
return;
}
int f1 = 2*no;
int f2 = 2*no+1;
int mid = (l+r)/2;
att(f1,l,mid,pos,val);
att(f2,mid+1,r,pos,val);
tr[no] = max(tr[f1],tr[f2]);
}
int qrr(int no, int l, int r, int L, int R) {
if(L > R) return 0;
if(l > R || r < L) return 0;
if(l >= L && r <= R) return tr[no];
int f1 = 2*no;
int f2 = 2*no+1;
int mid = (l+r)/2;
return max(qrr(f1,l,mid,L,R),qrr(f2,mid+1,r,L,R));
}
void atts(int no, int l, int r, int pos, int val) {
if(l > pos || r < pos) return;
if(l == r) {
trs[no]+= val;
return;
}
int f1 = 2*no;
int f2 = 2*no+1;
int mid = (l+r)/2;
atts(f1,l,mid,pos,val);
atts(f2,mid+1,r,pos,val);
trs[no] = trs[f1]+trs[f2];
}
int qrrs(int no, int l, int r, int L, int R) {
if(l > R || r < L) return 0;
if(l >= L && r <= R) return trs[no];
int f1 = 2*no;
int f2 = 2*no+1;
int mid = (l+r)/2;
return qrrs(f1,l,mid,L,R)+qrrs(f2,mid+1,r,L,R);
}
void solve() {
cin >> n >> q;
vector<int> cc;
for(int i = 1; i <= n; i++) {
cin >> a[i] >> b[i];
cc.pb(a[i]);
cc.pb(b[i]);
}
for(int i = 1; i <= q; i++) {
cin >> t[i];
cc.pb(t[i]);
}
sort(all(cc));
cc.erase(unique(all(cc)),cc.end());
int m = cc.size();
vector<pair<pair<int,int>,pair<int,int>>> qr;
for(int i = 1; i <= n; i++) {
int aux;
aux = a[i];
a[i] = upper_bound(all(cc),a[i]) - cc.begin();
ccval[a[i]] = aux;
aux = b[i];
b[i] = upper_bound(all(cc),b[i]) - cc.begin();
ccval[b[i]] = aux;
qr.pb(mp(mp(max(a[i],b[i]),0),mp(a[i],b[i])));
// cout << a[i] << " " << b[i] << endl;
}
for(int i = 1; i <= q; i++) {
t[i] = upper_bound(all(cc),t[i]) - cc.begin();
att(1,1,m,t[i],i);
qr.pb(mp(mp(t[i],1),mp(i,0)));
// cout << " att " << t[i] << " " << i << endl;
}
sort(all(qr),greater<pair<pair<int,int>,pair<int,int>>>());
int ans = 0;
for(auto X : qr) {
if(X.fr.sc == 0) {
//query
//primeiro pega a pos que vai ter que ver ate o final
int a1 = X.sc.fr;
int b1 = X.sc.sc;
// cout << a1 << " " << b1 << endl;
int pos = qrr(1,1,m,min(a1,b1),max(a1,b1)-1);
// cout << pos << endl;
if(pos == 0) pos = 1;
int qtd = qrrs(1,1,m,pos,q);
if(qtd%2 == 0) ans+= ccval[a1];
else ans+= ccval[b1];
}
else {
//att
int pos = X.sc.fr;
//adicionar 1 em pos
atts(1,1,m,pos,1);
}
}
cout << ans << endl;
}
int32_t main() {
ios::sync_with_stdio(false); cin.tie(0);
// freopen("in.in", "r", stdin);
//freopen("out.out", "w", stdout);
int tt = 1;
// cin >> tt;
while(tt--) solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
