Submission #985988

#	Time	Username	Problem	Language	Result	Execution time	Memory
985988		andrei_boaca	Examination (JOI19_examination)	C++17	43 / 100	909 ms	90304 KiB

examination

#include <bits/stdc++.h>

using namespace std;
int n,q,sol[100005];
vector<int> vals[4*100005],aint[4*100005];
int nrx,nry;
struct point
{
    int x,y,z;
} v[100005];
struct date
{
    int x,y,z,ind;
} qr[100005];
vector<int> vx,vy;
map<int,int> nrmx,nrmy;
bool byz(point a,point b)
{
    return a.z>b.z;
}
bool comp(date a, date b)
{
    return a.z>b.z;
}
void plsput(int nod,int st,int dr,int x,int y)
{
    vals[nod].push_back(y);
    if(st==dr)
        return;
    int mij=(st+dr)/2;
    if(x<=mij)
        plsput(nod*2,st,mij,x,y);
    else
        plsput(nod*2+1,mij+1,dr,x,y);
}
int getpoz(int ind,int val)
{
    int poz=vals[ind].size();
    poz++;
    int st=0;
    int dr=vals[ind].size();
    dr--;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if(vals[ind][mij]>=val)
        {
            poz=mij+1;
            dr=mij-1;
        }
        else
            st=mij+1;
    }
    return poz;
}
void build(int nod,int st,int dr)
{
    sort(vals[nod].begin(),vals[nod].end());
    vals[nod].erase(unique(vals[nod].begin(),vals[nod].end()),vals[nod].end());
    int lg=vals[nod].size();
    aint[nod].resize(4*lg+5);
    if(st==dr)
        return;
    int mij=(st+dr)/2;
    build(nod*2,st,mij);
    build(nod*2+1,mij+1,dr);
}
void upd2(int ind,int nod,int st,int dr,int poz,int val)
{
    if(st==dr)
    {
        aint[ind][nod]+=val;
        return;
    }
    int mij=(st+dr)/2;
    if(poz<=mij)
        upd2(ind,nod*2,st,mij,poz,val);
    else
        upd2(ind,nod*2+1,mij+1,dr,poz,val);
    aint[ind][nod]=aint[ind][nod*2]+aint[ind][nod*2+1];
}
int qr2(int ind,int nod,int st,int dr,int a,int b)
{
    if(st>=a&&dr<=b)
        return aint[ind][nod];
    int rez=0;
    int mij=(st+dr)/2;
    if(a<=mij)
        rez+=qr2(ind,nod*2,st,mij,a,b);
    if(b>mij)
        rez+=qr2(ind,nod*2+1,mij+1,dr,a,b);
    return rez;
}
void update(int nod,int st,int dr,int x,int y,int val)
{
    int poz=getpoz(nod,y);
    int lg=vals[nod].size();
    upd2(nod,1,1,lg,poz,val);
    if(st==dr)
        return;
    int mij=(st+dr)/2;
    if(x<=mij)
        update(nod*2,st,mij,x,y,val);
    else
        update(nod*2+1,mij+1,dr,x,y,val);
}
int query(int nod,int st,int dr,int a,int b,int y)
{
    if(st>=a&&dr<=b)
    {
        int poz=getpoz(nod,y);
        if(poz<=vals[nod].size())
            return qr2(nod,1,1,vals[nod].size(),poz,vals[nod].size());
        return 0;
    }
    int rez=0;
    int mij=(st+dr)/2;
    if(a<=mij)
        rez+=query(nod*2,st,mij,a,b,y);
    if(b>mij)
        rez+=query(nod*2+1,mij+1,dr,a,b,y);
    return rez;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i].x>>v[i].y;
        v[i].z=v[i].x+v[i].y;
        vx.push_back(v[i].x);
        vy.push_back(v[i].y);
    }
    for(int i=1;i<=q;i++)
    {
        cin>>qr[i].x>>qr[i].y>>qr[i].z;
        qr[i].ind=i;
        vx.push_back(qr[i].x);
        vy.push_back(qr[i].y);
    }
    sort(vx.begin(),vx.end());
    sort(vy.begin(),vy.end());
    vx.erase(unique(vx.begin(),vx.end()),vx.end());
    vy.erase(unique(vy.begin(),vy.end()),vy.end());
    nrx=vx.size();
    nry=vy.size();
    for(int i=0;i<vx.size();i++)
        nrmx[vx[i]]=i+1;
    for(int i=0;i<vy.size();i++)
        nrmy[vy[i]]=i+1;
    for(int i=1;i<=n;i++)
    {
        v[i].x=nrmx[v[i].x];
        v[i].y=nrmy[v[i].y];
    }
    for(int i=1;i<=q;i++)
    {
        qr[i].x=nrmx[qr[i].x];
        qr[i].y=nrmy[qr[i].y];
    }
    sort(v+1,v+n+1,byz);
    sort(qr+1,qr+q+1,comp);
    for(int i=1;i<=n;i++)
        plsput(1,1,nrx,v[i].x,v[i].y);
    build(1,1,nrx);
    int j=1;
    for(int i=1;i<=q;i++)
    {
        while(j<=n&&v[j].z>=qr[i].z)
        {
            update(1,1,nrx,v[j].x,v[j].y,+1);
            j++;
        }
        sol[qr[i].ind]=query(1,1,nrx,qr[i].x,nrx,qr[i].y);
    }
    for(int i=1;i<=q;i++)
        cout<<sol[i]<<'\n';
    return 0;
}

Compilation message (stderr)

examination.cpp: In function 'int query(int, int, int, int, int, int)':
examination.cpp:112:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |         if(poz<=vals[nod].size())
      |            ~~~^~~~~~~~~~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:149:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |     for(int i=0;i<vx.size();i++)
      |                 ~^~~~~~~~~~
examination.cpp:151:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |     for(int i=0;i<vy.size();i++)
      |                 ~^~~~~~~~~~

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