oj.uz

Submission #220248

# Submission time Handle Problem Language Result Execution time Memory
220248 2020-04-07T12:32:53 Z MKopchev Examination (JOI19_examination) C++14
100 / 100
 1942 ms 305896 KB 
#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

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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 14720 KB Output is correct
2 Correct 22 ms 14720 KB Output is correct
3 Correct 23 ms 14720 KB Output is correct
4 Correct 28 ms 14720 KB Output is correct
5 Correct 25 ms 14720 KB Output is correct
6 Correct 23 ms 14720 KB Output is correct
7 Correct 46 ms 19192 KB Output is correct
8 Correct 46 ms 19192 KB Output is correct
9 Correct 51 ms 19320 KB Output is correct
10 Correct 38 ms 17536 KB Output is correct
11 Correct 42 ms 17656 KB Output is correct
12 Correct 31 ms 14976 KB Output is correct
13 Correct 44 ms 19192 KB Output is correct
14 Correct 49 ms 19064 KB Output is correct
15 Correct 44 ms 19192 KB Output is correct
16 Correct 35 ms 16128 KB Output is correct
17 Correct 39 ms 15992 KB Output is correct
18 Correct 27 ms 14848 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1865 ms 295860 KB Output is correct
2 Correct 1852 ms 298596 KB Output is correct
3 Correct 1868 ms 298572 KB Output is correct
4 Correct 777 ms 165440 KB Output is correct
5 Correct 711 ms 139372 KB Output is correct
6 Correct 324 ms 21112 KB Output is correct
7 Correct 1732 ms 298132 KB Output is correct
8 Correct 1775 ms 298064 KB Output is correct
9 Correct 1603 ms 298252 KB Output is correct
10 Correct 448 ms 55344 KB Output is correct
11 Correct 427 ms 81784 KB Output is correct
12 Correct 228 ms 20216 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1865 ms 295860 KB Output is correct
2 Correct 1852 ms 298596 KB Output is correct
3 Correct 1868 ms 298572 KB Output is correct
4 Correct 777 ms 165440 KB Output is correct
5 Correct 711 ms 139372 KB Output is correct
6 Correct 324 ms 21112 KB Output is correct
7 Correct 1732 ms 298132 KB Output is correct
8 Correct 1775 ms 298064 KB Output is correct
9 Correct 1603 ms 298252 KB Output is correct
10 Correct 448 ms 55344 KB Output is correct
11 Correct 427 ms 81784 KB Output is correct
12 Correct 228 ms 20216 KB Output is correct
13 Correct 1755 ms 298492 KB Output is correct
14 Correct 1875 ms 298316 KB Output is correct
15 Correct 1823 ms 298676 KB Output is correct
16 Correct 739 ms 164344 KB Output is correct
17 Correct 715 ms 141036 KB Output is correct
18 Correct 333 ms 21112 KB Output is correct
19 Correct 1759 ms 298928 KB Output is correct
20 Correct 1848 ms 298968 KB Output is correct
21 Correct 1656 ms 299000 KB Output is correct
22 Correct 449 ms 55476 KB Output is correct
23 Correct 417 ms 81528 KB Output is correct
24 Correct 230 ms 20216 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 14720 KB Output is correct
2 Correct 22 ms 14720 KB Output is correct
3 Correct 23 ms 14720 KB Output is correct
4 Correct 28 ms 14720 KB Output is correct
5 Correct 25 ms 14720 KB Output is correct
6 Correct 23 ms 14720 KB Output is correct
7 Correct 46 ms 19192 KB Output is correct
8 Correct 46 ms 19192 KB Output is correct
9 Correct 51 ms 19320 KB Output is correct
10 Correct 38 ms 17536 KB Output is correct
11 Correct 42 ms 17656 KB Output is correct
12 Correct 31 ms 14976 KB Output is correct
13 Correct 44 ms 19192 KB Output is correct
14 Correct 49 ms 19064 KB Output is correct
15 Correct 44 ms 19192 KB Output is correct
16 Correct 35 ms 16128 KB Output is correct
17 Correct 39 ms 15992 KB Output is correct
18 Correct 27 ms 14848 KB Output is correct
19 Correct 1865 ms 295860 KB Output is correct
20 Correct 1852 ms 298596 KB Output is correct
21 Correct 1868 ms 298572 KB Output is correct
22 Correct 777 ms 165440 KB Output is correct
23 Correct 711 ms 139372 KB Output is correct
24 Correct 324 ms 21112 KB Output is correct
25 Correct 1732 ms 298132 KB Output is correct
26 Correct 1775 ms 298064 KB Output is correct
27 Correct 1603 ms 298252 KB Output is correct
28 Correct 448 ms 55344 KB Output is correct
29 Correct 427 ms 81784 KB Output is correct
30 Correct 228 ms 20216 KB Output is correct
31 Correct 1755 ms 298492 KB Output is correct
32 Correct 1875 ms 298316 KB Output is correct
33 Correct 1823 ms 298676 KB Output is correct
34 Correct 739 ms 164344 KB Output is correct
35 Correct 715 ms 141036 KB Output is correct
36 Correct 333 ms 21112 KB Output is correct
37 Correct 1759 ms 298928 KB Output is correct
38 Correct 1848 ms 298968 KB Output is correct
39 Correct 1656 ms 299000 KB Output is correct
40 Correct 449 ms 55476 KB Output is correct
41 Correct 417 ms 81528 KB Output is correct
42 Correct 230 ms 20216 KB Output is correct
43 Correct 1799 ms 305220 KB Output is correct
44 Correct 1822 ms 305624 KB Output is correct
45 Correct 1942 ms 305728 KB Output is correct
46 Correct 762 ms 172412 KB Output is correct
47 Correct 743 ms 144648 KB Output is correct
48 Correct 319 ms 21240 KB Output is correct
49 Correct 1839 ms 305896 KB Output is correct
50 Correct 1731 ms 305564 KB Output is correct
51 Correct 1668 ms 305320 KB Output is correct
52 Correct 480 ms 65596 KB Output is correct
53 Correct 455 ms 96632 KB Output is correct