#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
struct point{
int s;
int w;
int ind;
};
point wej[400003];
int odp[400003];
int zakr;
bool sorting(point a, point b){
if (a.s==b.s){
if (a.w==b.w)return a.ind<b.ind;
return a.w<b.w;
}
return a.s>b.s;
}
void init(int &n, int &q){
cin >> n >> q;
set<int> powt;
for (int i = 0; i<n; i++){
cin >> wej[i].s >> wej[i].w;
powt.insert(wej[i].w);
}
for (int i = 0; i<q; i++){
cin >> wej[n+i].s >> wej[n+i].w;
powt.insert(wej[n+i].w);
wej[n+i].ind=i+1;
}
int iter=0;
unordered_map<int,int> mp;
for (auto u : powt)mp[u]=++iter;
for (int i = 0; i<n+q; i++){
wej[i].w=mp[wej[i].w];
}
zakr=iter;
}
const int base=1<<19;
int tree[2*base];
void zmien(int v, int x){
v+=base;
tree[v]+=x;
v>>=1;
while(v){
tree[v]=tree[2*v]+tree[2*v+1];
v>>=1;
}
}
int sprawdz(int a, int b){
a+=base-1;
b+=base+1;
int ans=0;
while(a/2!=b/2){
if (!(a&1))ans+=tree[a+1];
if (b&1)ans+=tree[b-1];
a>>=1;
b>>=1;
}
return ans;
}
int znajdz(int v, int val){
if (v>=base)return v-base;
if (tree[2*v]>=val)return znajdz(2*v,val);
else return znajdz(2*v+1,val-tree[2*v]);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n,q,now,nxt;
init(n,q);
sort(wej,wej+n+q,sorting);
for (int i = 0; i<n+q; i++){
now=sprawdz(1,wej[i].w);
if (wej[i].ind){
odp[wej[i].ind]=now;
}
else{
nxt=znajdz(1,now+1);
if (nxt<=zakr)zmien(nxt,-1);
zmien(wej[i].w,1);
}
}
for (int i = 1; i<=q; i++){
cout << odp[i] << '\n';
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
