Submission #1308766

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308766		zhivko	Examination (JOI19_examination)	C++20	0 / 100	542 ms	22636 KiB

examination

#include<bits/stdc++.h>
using namespace std;
struct pont
{
    long long x,y,z;
    bool quer;
    bool type;
    int id;
    pont(){};
    pont(long long xxx,long long yi,long long zh,int t,bool qu)
    {
        x=xxx;
        y=yi;
        z=zh;
        id=t;
        quer=qu;
    }
};
long long e=0;
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[1000001];
void mrpropa()
{
    for(long long i=0;i<=e;i++)
    {
        hrast[i].clean();
    }
    e=0;
}
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;
}
long long query(long long v,long long l,long long r,long long ql,long long qr)
{
    if(l>qr||r<ql||l>r)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;
    if(a.z!=b.z)return a.z>b.z;
    return a.quer<b.quer;
}
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&&v[i].type==0)
        {
            update(0,0,mz,v[i].z);
            //cout<<v[i].id<<" "<<v[i].z<<"update "<<v[i].quer<<endl;
        }
        if(v[i].quer==1&&v[i].type==1)
        {
            ans[v[i].id]+=query(0,0,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++)
    {
        gr.push_back(c[i-1]);
        gr.back().type=0;
    }
    for(long long i=mid+1;i<=r;i++)
    {
        gr.push_back(c[i-1]);
        gr.back().type=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;
}

Compilation message (stderr)

examination.cpp: In function 'void read()':
examination.cpp:86:31: warning: narrowing conversion of 'i' from 'long long int' to 'int' [-Wnarrowing]
   86 |         c.push_back({xh,yh,zh,i,0});
      |                               ^
examination.cpp:92:31: warning: narrowing conversion of 'i' from 'long long int' to 'int' [-Wnarrowing]
   92 |         c.push_back({xh,yh,zh,i,1});
      |                               ^

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