Submission #1287556

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287556		simona1230	Examination (JOI19_examination)	C++20	0 / 100	374 ms	8620 KiB

examination

#include <bits/stdc++.h>

using namespace std;
int n,q;
struct student
{
    int x,y,z,i;
    student(){}
    student(int _x,int _y,int _z,int _i)
    {
        x=_x;
        y=_y;
        z=_z;
        i=_i;
    }

    bool operator<(const student&s)const
    {
        return z>s.z;
    }
};

bool cmpa(student s1,student s2)
{
    return s1.x>s2.x;
}

int ans[200001];
student a[200001];
int t[800001];
void upd(int i,int l,int r,int id,int x)
{
    if(l==r)
    {
        t[i]+=x;
        return;
    }

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

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

int query(int i,int l,int r,int id)
{
    if(l==r)return t[i];
    int m=(l+r)/2;
    if(m<id)return query(i*2+1,m+1,r,id);
    return query(i*2,l,m,id)+t[i*2+1];
}

int cnt=1;

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

    int m=(l+r)/2;
    solve(l,m);
    solve(m+1,r);

    vector<student> v1,v2;
    //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(),cmpa);
    sort(v2.begin(),v2.end(),cmpa);

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

        //cout<<" = "<<v2[i].i<<" "<<query(1,1,cnt,v2[i].y)<<endl;
        ans[v2[i].i]+=query(1,1,cnt,v2[i].y);
    }

    for(int i=0;i<j;i++)
        if(v1[i].i==-1)
            upd(1,1,cnt,v1[i].y,-1);
}


bool cmp(student s1,student s2)
{
    return s1.y<s2.y;
}

void read()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        cin>>x>>y;
        a[i]={x,y,x+y,-1};
    }

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

    sort(a+1,a+n+q+1,cmp);

    for(int i=1;i<=n+q;i++)
    {
        int add=0;
        if(i!=n+q&&a[i].y!=a[i+1].y)add++;
        a[i].y=cnt;
        cnt+=add;
    }

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

    /*cout<<endl;
    for(int i=1;i<=n+q;i++)
        cout<<a[i].x<<" "<<a[i].y<<" "<<a[i].z<<" "<<a[i].i<<endl;
    cout<<endl;*/
}



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;i++)
        cout<<ans[i]<<endl;

	return 0;
}

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