Submission #220248

#	Time	Username	Problem	Language	Result	Execution time	Memory
220248		MKopchev	Examination (JOI19_examination)	C++14	100 / 100	1942 ms	305896 KiB

examination

#include<bits/stdc++.h>
using namespace std;
const int nmax=(1<<17)+42;
int n,q;

struct info
{
    int first_low,second_low,sum_low,id;
};

info inp[2*nmax];

bool cmp(info a,info b)
{
    if(a.sum_low!=b.sum_low)return a.sum_low>b.sum_low;
    return a.id<b.id;
}
int x_vals[nmax];
int y_vals[nmax];

int output[nmax];

struct tree_node
{
    int l,r,sum;
};

vector< tree_node > tree[2*nmax];

int make_node(int where)
{
    tree_node ret;
    ret.l=-1;
    ret.r=-1;
    ret.sum=0;
    tree[where].push_back(ret);

    return tree[where].size()-1;
}

void update_cur_tree(int node_pointer,int node,int l,int r,int y_val)
{
    //cout<<"update_cur_tree "<<node_pointer<<" "<<node<<" "<<l<<" "<<r<<" "<<y_val<<endl;

    tree[node_pointer][node].sum++;
    if(l==r)return;

    int av=(l+r)/2;
    if(y_val<=av)
    {
        if(tree[node_pointer][node].l==-1)
        {
            int was=make_node(node_pointer);
            tree[node_pointer][node].l=was;
        }
        update_cur_tree(node_pointer,tree[node_pointer][node].l,l,av,y_val);
    }
    else
    {
        if(tree[node_pointer][node].r==-1)
        {
            int was=make_node(node_pointer);
            tree[node_pointer][node].r=was;
        }
        update_cur_tree(node_pointer,tree[node_pointer][node].r,av+1,r,y_val);
    }
}
void update(int node,int l,int r,int x_val,int y_val)
{
    update_cur_tree(node,0,1,n,y_val);

    if(l==r)return;

    int av=(l+r)/2;
    if(x_val<=av)update(node*2,l,av,x_val,y_val);
    else update(node*2+1,av+1,r,x_val,y_val);
}

int query_cur_tree(int node_pointer,int node,int l,int r,int lq,int rq)
{
    if(node==-1)return 0;

    if(l==lq&&r==rq)return tree[node_pointer][node].sum;

    int av=(l+r)/2,ret=0;

    if(lq<=av)ret=ret+query_cur_tree(node_pointer,tree[node_pointer][node].l,l,av,lq,min(av,rq));
    if(av<rq)ret=ret+query_cur_tree(node_pointer,tree[node_pointer][node].r,av+1,r,max(av+1,lq),rq);

    return ret;
}
int query(int node,int l,int r,int x_left,int x_right,int y_left,int y_right)
{
    if(l==x_left&&r==x_right)return query_cur_tree(node,0,1,n,y_left,y_right);

    int ret=0,av=(l+r)/2;

    if(x_left<=av)ret=ret+query(node*2,l,av,x_left,min(x_right,av),y_left,y_right);
    if(av<x_right)ret=ret+query(node*2+1,av+1,r,max(x_left,av+1),x_right,y_left,y_right);

    return ret;
}
int main()
{
    for(int i=0;i<2*nmax;i++)make_node(i);

    scanf("%i%i",&n,&q);

    for(int i=1;i<=n;i++)
    {
        scanf("%i%i",&inp[i].first_low,&inp[i].second_low);
        inp[i].sum_low=inp[i].first_low+inp[i].second_low;

        x_vals[i]=inp[i].first_low;
        y_vals[i]=inp[i].second_low;

        inp[i].id=-1;
    }

    for(int i=n+1;i<=n+q;i++)
    {
        scanf("%i%i%i",&inp[i].first_low,&inp[i].second_low,&inp[i].sum_low);
        inp[i].id=i-n;
    }

    sort(inp+1,inp+n+q+1,cmp);
    sort(x_vals+1,x_vals+n+1);
    sort(y_vals+1,y_vals+n+1);

    for(int i=1;i<=n+q;i++)
    {
        int x_actual=lower_bound(x_vals+1,x_vals+n+1,inp[i].first_low)-x_vals;
        int y_actual=lower_bound(y_vals+1,y_vals+n+1,inp[i].second_low)-y_vals;

        if(inp[i].id==-1)
        {
            update(1,1,n,x_actual,y_actual);
        }
        else if(x_actual<=n&&y_actual<=n)
        {
            output[inp[i].id]=query(1,1,n,x_actual,n,y_actual,n);
        }
    }

    for(int i=1;i<=q;i++)
        printf("%i\n",output[i]);
    return 0;
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:107:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i",&n,&q);
     ~~~~~^~~~~~~~~~~~~~
examination.cpp:111:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i%i",&inp[i].first_low,&inp[i].second_low);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:122:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i%i%i",&inp[i].first_low,&inp[i].second_low,&inp[i].sum_low);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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