Submission #1291254

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291254		simona1230	Examination (JOI19_examination)	C++20	100 / 100	846 ms	20828 KiB

examination

#include <bits/stdc++.h>

using namespace std;

struct hey
{
    int x,y,z,i;
    hey(){}
    hey(int _x,int _y,int _z,int _i)
    {
        x=_x;
        y=_y;
        z=_z;
        i=_i;
    }
};

int n,q;
hey a[200001];
vector<int> h;
map<int,int> mp;

bool cmpz(hey h1,hey h2)
{
    if(h1.z==h2.z)return h1.i>h2.i;
    return h1.z<h2.z;
}

void read()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].x>>a[i].y;
        h.push_back(a[i].y);
        a[i].z=a[i].x+a[i].y;
    }

    for(int i=1;i<=q;i++)
    {
        cin>>a[i+n].x>>a[i+n].y>>a[i+n].z;
        h.push_back(a[i+n].y);
        a[i+n].i=i;
    }

    sort(h.begin(),h.end());
    int id=0;
    for(int i=0;i<h.size();i++)
    {
        if(!i||h[i]!=h[i-1])id++;
        mp[h[i]]=id;
    }

    for(int i=1;i<=n+q;i++)
        a[i].y=mp[a[i].y];

    sort(a+1,a+n+q+1,cmpz);
}

int t[800001];
void upd(int i,int l,int r,int id,int vl)
{
    if(l==r)
    {
        t[i]+=vl;
        return;
    }

    int m=(l+r)/2;
    if(id<=m)upd(i*2,l,m,id,vl);
    else upd(i*2+1,m+1,r,id,vl);

    t[i]=t[i*2]+t[i*2+1];
}

int query(int i,int l,int r,int ql,int qr)
{
    if(ql>qr)return 0;
    if(ql<=l&&r<=qr)return t[i];
    int m=(l+r)/2;
    return query(i*2,l,m,ql,min(qr,m))+query(i*2+1,m+1,r,max(m+1,ql),qr);
}

bool cmpx(hey h1,hey h2)
{
    return h1.x<h2.x;
}

int ans[200001];

void solve(int l,int r)
{
    if(l>=r)return;

    vector<hey> v1,v2;
    int m=(l+r)/2;

    solve(l,m);
    solve(m+1,r);
    //cout<<l<<" -- "<<r<<endl;

    for(int i=l;i<=m;i++)
        v1.push_back(a[i]);
    for(int i=m+1;i<=r;i++)
        v2.push_back(a[i]);

    sort(v1.begin(),v1.end(),cmpx);
    sort(v2.begin(),v2.end(),cmpx);

    int j=v2.size()-1;
    for(int i=v1.size()-1;i>=0;i--)
    {
        while(j>=0&&v1[i].x<=v2[j].x)
        {
            if(v2[j].i==0)
            {
                //cout<<"+ "<<v2[j].y<<endl;
                upd(1,1,n+q,v2[j].y,1);
            }
            j--;
        }

        //cout<<"? "<<v1[i].y<<" "<<query(1,1,n+q,v1[i].y,n+q)<<endl;
        ans[v1[i].i]+=query(1,1,n+q,v1[i].y,n+q);
    }

    for(int i=j+1;i<v2.size();i++)
        if(v2[i].i==0)upd(1,1,n+q,v2[i].y,-1);
}


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	read();
	solve(1,n+q);
	//for(int i=1;i<=q+n;i++)
    //    cout<<a[i].x<<" "<<a[i].y<<" "<<a[i].z<<" "<<a[i].i<<endl;
	for(int i=1;i<=q;i++)
        cout<<ans[i]<<endl;
	return 0;
}

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57