Submission #854691

#	Time	Username	Problem	Language	Result	Execution time	Memory
854691		DobromirAngelov	Examination (JOI19_examination)	C++14	0 / 100	217 ms	12036 KiB

examination

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;

const int MAXN=1e5+5;
const int MAXQ=1e5+5;

struct point
{
    int x,y,z,num;
};

int n,q;
int mx;
point p[MAXN+MAXQ];
int tree[MAXN+MAXQ];
int ans[MAXQ];

void update(int idx,int val)
{
    while(idx<=mx)
    {
        tree[idx]+=val;
        idx+=idx&(-idx);
    }
}

int query(int idx)
{
    int ret=0;
    while(idx>0)
    {
        ret+=tree[idx];
        idx-=idx&(-idx);
    }
    return ret;
}

void cdq(int l,int r)
{
    if(l+1>=r) return;

    int mid=(l+r)/2;

    cdq(l,mid);
    cdq(mid,r);

    vector<int> hist;
    vector<point> tmp;
    int ptr1=l, ptr2=mid;
    int cntl=0;
    while(ptr1<mid && ptr2<r)
    {
        if(p[ptr1].y>=p[ptr2].y)
        {
            if(!p[ptr1].num)
            {
                update(p[ptr1].z,1);
                hist.push_back(p[ptr1].z);
                cntl++;
            }
            tmp.push_back(p[ptr1++]);
        }
        else
        {
            if(p[ptr2].num) ans[p[ptr2].num]+=cntl-query(p[ptr2].z-1);
            tmp.push_back(p[ptr2++]);
        }
    }
    while(ptr1<mid) tmp.push_back(p[ptr1++]);
    while(ptr2<r)
    {
        if(p[ptr2].num) ans[p[ptr2].num]+=cntl-query(p[ptr2].z-1);
        tmp.push_back(p[ptr2++]);
    }

    for(int i=0;i<hist.size();i++) update(hist[i], -1);
    for(int i=l;i<r;i++) p[i]=tmp[i-l];

    return;
}

bool cmpx(point a,point b) {return a.x<b.x;}
bool cmpy(point a,point b) {return a.y<b.y;}
bool cmpz(point a,point b) {return a.z<b.z;}

void compress()
{
    p[0].x=p[0].y=p[0].z=-1;
    sort(p+1,p+n+q+1,cmpx);
    int ptr=0;
    for(int i=1;i<=n+q;i++)
    {
        if(p[i].x!=p[i-1].x) ptr++;
        p[i].x=ptr;
    }
    sort(p+1,p+n+q+1,cmpy);

    ptr=0;
    for(int i=1;i<=n+q;i++)
    {
        if(p[i].y!=p[i-1].y) ptr++;
        p[i].y=ptr;
    }
    sort(p+1,p+n+q+1,cmpz);

    ptr=0;
    for(int i=1;i<=n+q;i++)
    {
        if(p[i].z!=p[i-1].z) ptr++;
        p[i].z=ptr;
    }
    mx=p[n+q].z+1;
}

bool cmp(point a,point b)
{
    if(a.x==b.x)
    {
        if((a.num && b.num) || (!a.num && !b.num))
        {
            if(a.y==b.y) return a.z>b.z;
            return a.y>b.y;
        }
        return a.num<b.num;
    }
    return a.x>b.x;
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

cin>>n>>q;
for(int i=1;i<=n;i++)
{
    cin>>p[i].x>>p[i].y;
    p[i].z=p[i].x+p[i].y;
    p[i].num=0;
}
for(int i=n+1;i<=n+q;i++)
{
    cin>>p[i].x>>p[i].y>>p[i].z;
    p[i].num=i-n;
}

compress();

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

cdq(1,n+q+1);

for(int i=1;i<=q;i++) cout<<ans[i]<<endl;

return 0;
}

Compilation message (stderr)

examination.cpp: In function 'void cdq(int, int)':
examination.cpp:78:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for(int i=0;i<hist.size();i++) update(hist[i], -1);
      |                 ~^~~~~~~~~~~~

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