Submission #1308488

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308488		zhivko	Examination (JOI19_examination)	C++20	Compilation error	0 ms	0 KiB

examination

#include<bits/stdc++.h>
using namespace std;
struct pont
{
    long long x,y,z;
    bool quer;
    long long id;
    pont(){};
    pont(long long xxx,long long yi,long long zh,long long t,bool qu)
    {
        x=xxx;
        y=yi;
        z=zh;
        id=t;
        quer=qu;
    }
};
long long e=1;
struct segs
{
    long long sum=0,cl=-1,cr=-1;
    void clean()
    {
        sum=0;
        cl=-1;
        cr=-1;
    }
    void fuck()
    {
        cl=++e;
        cr=++e;
    }
};

long long mz=0;
segs hrast[10000001];
void mrpropa()
{
    for(long long i=1;i<=e;i++)
    {
        hrast[i].clean();
    }
    e=1;
}
long long n,q;
vector<pont>c;
long long ans[100001];
void update(long long v,long long l,long long r,long long c)
{

    if(l==r)
    {
        hrast[v].sum++;
        return;
    }
    long long mid=(l+r)/2;
    if(hrast[v].cl==-1)hrast[v].fuck();
    if(c<=mid)update(hrast[v].cl,l,mid,c);
    else update(hrast[v].cr,mid+1,r,c);
    hrast[v].sum=hrast[hrast[v].cl].sum+hrast[hrast[v].cr].sum;
    //cout<<hrast[v].sum<<" "<<l<<" "<<r<<" upd "<<c<<endl;
    //if(v==1)cout<<"extra "<<hrast[hrast[v].cl].sum<<" "<<hrast[hrast[v].cr].sum<<endl;
}
long long query(long long v,long long l,long long r,long long ql,long long qr)
{
    if(l>qr||r<ql)return 0;

    if(l>=ql&&r<=qr)
    {
        return hrast[v].sum;
    }
    long long mid=(l+r)/2;
    if(hrast[v].cl==-1)return 0;
    return query(hrast[v].cl,l,mid,ql,qr)+query(hrast[v].cr,mid+1,r,ql,qr);
}
bool cmp(pont a,pont b)
{
    return a.x>b.x;
}
void read()
{
    cin>>n>>q;
    long long xh,yh,zh;
    for(long long i=1;i<=n;i++)
    {
        cin>>xh>>yh;
        zh=xh+yh;
        mz=max(zh,mz);
        c.push_back({xh,yh,zh,i,0});
    }
    for(long long i=0;i<q;i++)
    {
        cin>>xh>>yh>>zh;
        mz=max(zh,mz);
        c.push_back({xh,yh,zh,i,1});
    }
    sort(c.begin(),c.end(),cmp);
}
bool cmp2(pont a,pont b)
{
    if(a.y!=b.y)return a.y>b.y;
    return a.z>b.z;
}
void solve(vector<pont>& v)
{
    sort(v.begin(),v.end(),cmp2);
    for(long long i=0;i<v.size();i++)
    {
        if(v[i].quer==0)
        {
            update(1,1,mz,v[i].z);
            //cout<<v[i].id<<" "<<v[i].z<<"update "<<v[i].quer<<endl;
        }
        if(v[i].quer==1)
        {
            ans[v[i].id]+=query(1,1,mz,v[i].z,mz);
            //cout<<v[i].id<<" "<<ans[v[i].id]<<"sere mi se"<<endl;
        }
    }
}
void fein(long long l,long long r)
{
    if(l==r)
    {
        return;
    }
    long long mid=(l+r)/2;
    fein(l,mid);
    fein(mid+1,r);
    vector<pont>gr;
    for(long long i=l;i<=mid;i++)
    {
        if(c[i-1].quer==0)gr.push_back(c[i-1]);
    }
    for(long long i=mid+1;i<=r;i++)
    {
        if(c[i-1].quer==1)gr.push_back(c[i-1]);
    }
    //cout<<l<<" "<<r<<endl;
    solve(gr);
    mrpropa();
}
void print()
{
    for(long long i=0;i<q;i++)
    {
        cout<<ans[i]<<endl;
    }
}
int main()
{
	ios_base::sync_with_stdio(0);
    	cin.tie(0);
    	cout.tie(0);
    read();
    fein(1,n+q);
    print();
	return 0;
}