Submission #127395

#	Time	Username	Problem	Language	Result	Execution time	Memory
127395		Bodo171	Examination (JOI19_examination)	C++14	100 / 100	2416 ms	526000 KiB

examination

#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;
const int nmax=100005;
struct ev
{
    int v1,v2,v3,wh;
}v[2*nmax];
int n,q,i,x,y,z,poz;
int b[2][nmax],aib[nmax],ans[nmax];
bool cmp(ev unu,ev doi)
{
    if(unu.v1==doi.v1) return (unu.wh<doi.wh);
    return (unu.v1>doi.v1);
}
int cb(int wh,int val)
{
    int ret=0;
    for(int p=16;p>=0;p--)
        if(ret+(1<<p)<=n&&b[wh][ret+(1<<p)]<val)
            ret+=(1<<p);
    ret++;
    return ret;
}
struct node
{
    int sum;
    node *ls,*rs;
    node()
    {
        sum=0;ls=0;rs=0;
    }
}*arb[4*nmax];
int S,p1,p2;
void query_y(node *nod,int l,int r,int st,int dr)
{
    if(st<=l&&r<=dr)
    {
        S+=nod->sum;
        return;
    }
    int m=(l+r)/2;
    if(st<=m&&nod->ls) query_y(nod->ls,l,m,st,dr);
    if(m<dr&&nod->rs)  query_y(nod->rs,m+1,r,st,dr);
}
void query(int nod,int l,int r,int st_x,int dr_x,int st_y,int dr_y)
{
    if(st_x<=l&&r<=dr_x)
    {
        query_y(arb[nod],1,n,st_y,dr_y);
        return;
    }
    int m=(l+r)/2;
    if(st_x<=m) query(2*nod,l,m,st_x,dr_x,st_y,dr_y);
    if(m<dr_x)  query(2*nod+1,m+1,r,st_x,dr_x,st_y,dr_y);
}
void update_y(node *nod,int l,int r,int poz)
{
    nod->sum++;
    if(l==r) return;
    int m=(l+r)/2;
    if(poz<=m)
    {
        if(!nod->ls) nod->ls=new node;
        update_y(nod->ls,l,m,poz);
    }
    else
    {
        if(!nod->rs) nod->rs=new node;
        update_y(nod->rs,m+1,r,poz);
    }
}
void update(int nod,int l,int r,int pozx,int pozy)
{
    update_y(arb[nod],1,n,pozy);
    if(l==r) return;
    int m=(l+r)/2;
    if(pozx<=m) update(2*nod,l,m,pozx,pozy);
    else update(2*nod+1,m+1,r,pozx,pozy);
}
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n>>q;
    for(i=1;i<=n;i++)
    {
        cin>>v[i].v1>>v[i].v2;
        v[i].v3=v[i].v1+v[i].v2;
        b[0][i]=v[i].v2;
        b[1][i]=v[i].v1+v[i].v2;
    }
    for(i=0;i<2;i++)
    {
        sort(b[i]+1,b[i]+n+1);
    }
    for(i=1;i<=q;i++)
    {
        cin>>x>>y>>z;
        v[n+i].v1=x;
        v[n+i].v2=y;
        v[n+i].v3=z;
        v[n+i].wh=i;
    }
    sort(v+1,v+n+q+1,cmp);
    for(i=1;i<=4*n;i++)
        arb[i]=new node;
    for(i=1;i<=n+q;i++)
    {
        p1=cb(0,v[i].v2);
        p2=cb(1,v[i].v3);
        if(v[i].wh)
        {
            S=0;
            if(p1<=n&&p2<=n)query(1,1,n,p1,n,p2,n);
            ans[v[i].wh]=S;
        }
        else
        {
            update(1,1,n,p1,p2);
        }
    }
    for(i=1;i<=q;i++)
        cout<<ans[i]<<'\n';
    return 0;
}

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