제출 #1288008

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288008		simona1230	Examination (JOI19_examination)	C++20	0 / 100	2193 ms	23088 KiB

examination

#include <bits/stdc++.h>

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

    bool operator<(const student&s)const
    {
        if(z==s.z)
        {
            if(x==s.x)
            {
                if(y==s.y)
                {
                    return s.i!=-1;
                }

                return y>s.y;
            }

            return x>s.x;
        }
        return z>s.z;
    }
};

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

        return s1.x>s2.x;
}

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

    long long 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];
}

long long query(long long i,long long l,long long r,long long id)
{
    if(l==r)return t[i];
    long long 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];
}

long long cnt=1;

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

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

    vector<student> v1,v2;
    //cout<<l<<" ! "<<r<<endl;

    for(long long i=l; i<=m; i++)
    {
        v1.push_back(a[i]);
    }

    for(long long i=m+1; i<=r; i++)
    {
        v2.push_back(a[i]);
    }

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

    long long j=0;
    for(long long 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(long long 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(long long i=1; i<=n; i++)
    {
        long long x,y;
        cin>>x>>y;
        a[i]= {x,y,x+y,-1};
    }

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

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

    for(long long i=1; i<=n+q; i++)
    {
        long long 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(long long 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(long long 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