Submission #1308284

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

examination

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

int mz=0;
segs hrast[100000001];
void mrpropa()
{
    e=1;
    for(int i=1;i<=mz;i++)
    {
        hrast[i].clean();
    }
}
int n,q;
vector<pont>c;
int ans[100001];
void update(int v,int l,int r,int c)
{
    if(l==r)
    {
        hrast[v].sum++;
        return;
    }
    int 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;
}
int query(int v,int l,int r,int ql,int qr)
{
    if(l>qr||r<ql)return 0;
    if(l>=ql&&r<=qr)
    {
        return hrast[v].sum;
    }
    int 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;
    int xh,yh,zh;
    for(int i=1;i<=n;i++)
    {
        cin>>xh>>yh;
        zh=xh+yh;
        mz=max(zh,mz);
        c.push_back({xh,yh,zh,i,0});
    }
    for(int 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(int i=0;i<v.size();i++)
    {
        if(v[i].type==0&&v[i].quer==0)update(1,1,mz,v[i].z);
        else if(v[i].quer==1)ans[v[i].id]+=query(1,1,mz,v[i].z,mz);
    }
}
void fein(int l,int r)
{
    if(l==r)
    {
        return;
    }
    int mid=(l+r)/2;
    fein(l,mid);
    fein(mid+1,r);
    vector<pont>gr;
    for(int i=l;i<=mid;i++)
    {
        gr.push_back(c[i-1]);
        gr[gr.size()-1].type=0;
    }
    for(int i=mid+1;i<=r;i++)
    {
        gr.push_back(c[i-1]);
        gr[gr.size()-1].type=1;
    }
    solve(gr);
    mrpropa();
}
void print()
{
    for(int 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;
}