| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 380582 | mariowong | Examination (JOI19_examination) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
struct node{
long long maths,ict,sum;
int indx;
}a[200005];
bool cmp(node a1,node a2){
return a1.maths < a2.maths;
}
int n,m,pt,seg[800005];
pair <long long,int> d[200005];
long long ct,now,ans[200005];
vector <pair<long long,long long> > u;
vector <pair<pair<long long,long long>,int> > q;
void build (int id,int x,int y){
if (x == y)
seg[id]=0;
else
{
int mid=(x+y)/2;
if (seg[id] != 0){
build(id*2,x,mid);
build(id*2+1,mid+1,y);
}
seg[id]=0;
}
}
void update(int id,int x,int y,int pos){
if (x == y)
seg[id]++;
else
{
int mid=(x+y)/2;
if (pos <= mid) update(id*2,x,mid,pos);
else update(id*2+1,mid+1,y,pos);
seg[id]=seg[id*2]+seg[id*2+1];
}
}
int query(int id,int x,int y,int l,int r){
if (l <= x && y <= r)
return seg[id];
if (l > y || r < x)
return 0;
int mid=(x+y)/2;
return query(id*2,x,mid,l,r)+query(id*2+1,mid+1,y,l,r);
}
void solve(int x,int y){
if (x == y);
else
{
int mid=(x+y)/2;
u.clear(); q.clear();
build(1,1,ct);
for (int i=x;i<=mid;i++){
if (a[i].indx == 0)
u.push_back(make_pair(a[i].ict,a[i].sum));
}
for (int i=mid+1;i<=y;i++){
if (a[i].indx != 0)
q.push_back(make_pair(make_pair(a[i].ict,a[i].sum),a[i].indx));
}
sort(u.begin(),u.end()); sort(q.begin(),q.end());
reverse(u.begin(),u.end()); reverse(q.begin(),q.end());
pt=0;
for (int i=0;i<q.size();i++){
while (pt < (int)u.size() && u[pt].first >= q[i].first.first){
update(1,1,ct,u[pt].second);
pt++;
}
ans[q[i].second]+=query(1,1,ct,q[i].first.second,ct);
}
solve(x,mid);
solve(mid+1,y);
}
}
int main(){
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i=1;i<=n;i++){
cin >> a[i].maths >> a[i].ict;
a[i].sum=a[i].maths+a[i].ict;
d[i]=make_pair(a[i].sum,i);
}
for (int i=n+1;i<=n+m;i++){
cin >> a[i].maths >> a[i].ict >> a[i].sum; a[i].indx=i-n;
d[i]=make_pair(a[i].sum,i);
}
sort(d+1,d+1+n+m); now=1;
d[n+m+1]=1e18;
for (int i=2;i<=n+m+1;i++){
if (d[i].first != d[i-1].first){
ct++;
for (int j=now;j<i;j++){
a[d[j].second].sum=ct;
}
now=i;
}
}
sort(a+1,a+1+n+m,cmp); reverse(a+1,a+1+n+m);
solve(1,n+m);
for (int i=1;i<=m;i++){
cout << ans[i] << "\n";
}
return 0;
}