oj.uz

Submission #127395

# Submission time Handle Problem Language Result Execution time Memory
127395 2019-07-09T10:15:45 Z Bodo171 Examination (JOI19_examination) C++14
100 / 100
 2416 ms 526000 KB 
#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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 26 ms 8952 KB Output is correct
8 Correct 26 ms 8952 KB Output is correct
9 Correct 26 ms 8952 KB Output is correct
10 Correct 18 ms 6264 KB Output is correct
11 Correct 19 ms 5112 KB Output is correct
12 Correct 9 ms 1400 KB Output is correct
13 Correct 25 ms 8952 KB Output is correct
14 Correct 25 ms 8952 KB Output is correct
15 Correct 25 ms 8952 KB Output is correct
16 Correct 18 ms 5072 KB Output is correct
17 Correct 12 ms 3576 KB Output is correct
18 Correct 7 ms 1068 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1978 ms 517804 KB Output is correct
2 Correct 1898 ms 517868 KB Output is correct
3 Correct 2110 ms 518156 KB Output is correct
4 Correct 770 ms 264568 KB Output is correct
5 Correct 1431 ms 198864 KB Output is correct
6 Correct 320 ms 22776 KB Output is correct
7 Correct 1953 ms 518080 KB Output is correct
8 Correct 1956 ms 518384 KB Output is correct
9 Correct 1895 ms 517824 KB Output is correct
10 Correct 1305 ms 176472 KB Output is correct
11 Correct 432 ms 112120 KB Output is correct
12 Correct 246 ms 21492 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1978 ms 517804 KB Output is correct
2 Correct 1898 ms 517868 KB Output is correct
3 Correct 2110 ms 518156 KB Output is correct
4 Correct 770 ms 264568 KB Output is correct
5 Correct 1431 ms 198864 KB Output is correct
6 Correct 320 ms 22776 KB Output is correct
7 Correct 1953 ms 518080 KB Output is correct
8 Correct 1956 ms 518384 KB Output is correct
9 Correct 1895 ms 517824 KB Output is correct
10 Correct 1305 ms 176472 KB Output is correct
11 Correct 432 ms 112120 KB Output is correct
12 Correct 246 ms 21492 KB Output is correct
13 Correct 2215 ms 518244 KB Output is correct
14 Correct 2143 ms 518460 KB Output is correct
15 Correct 1956 ms 518020 KB Output is correct
16 Correct 915 ms 263860 KB Output is correct
17 Correct 1568 ms 199032 KB Output is correct
18 Correct 329 ms 22796 KB Output is correct
19 Correct 2099 ms 518820 KB Output is correct
20 Correct 2187 ms 518668 KB Output is correct
21 Correct 2416 ms 518616 KB Output is correct
22 Correct 1295 ms 176560 KB Output is correct
23 Correct 428 ms 111976 KB Output is correct
24 Correct 246 ms 21496 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 26 ms 8952 KB Output is correct
8 Correct 26 ms 8952 KB Output is correct
9 Correct 26 ms 8952 KB Output is correct
10 Correct 18 ms 6264 KB Output is correct
11 Correct 19 ms 5112 KB Output is correct
12 Correct 9 ms 1400 KB Output is correct
13 Correct 25 ms 8952 KB Output is correct
14 Correct 25 ms 8952 KB Output is correct
15 Correct 25 ms 8952 KB Output is correct
16 Correct 18 ms 5072 KB Output is correct
17 Correct 12 ms 3576 KB Output is correct
18 Correct 7 ms 1068 KB Output is correct
19 Correct 1978 ms 517804 KB Output is correct
20 Correct 1898 ms 517868 KB Output is correct
21 Correct 2110 ms 518156 KB Output is correct
22 Correct 770 ms 264568 KB Output is correct
23 Correct 1431 ms 198864 KB Output is correct
24 Correct 320 ms 22776 KB Output is correct
25 Correct 1953 ms 518080 KB Output is correct
26 Correct 1956 ms 518384 KB Output is correct
27 Correct 1895 ms 517824 KB Output is correct
28 Correct 1305 ms 176472 KB Output is correct
29 Correct 432 ms 112120 KB Output is correct
30 Correct 246 ms 21492 KB Output is correct
31 Correct 2215 ms 518244 KB Output is correct
32 Correct 2143 ms 518460 KB Output is correct
33 Correct 1956 ms 518020 KB Output is correct
34 Correct 915 ms 263860 KB Output is correct
35 Correct 1568 ms 199032 KB Output is correct
36 Correct 329 ms 22796 KB Output is correct
37 Correct 2099 ms 518820 KB Output is correct
38 Correct 2187 ms 518668 KB Output is correct
39 Correct 2416 ms 518616 KB Output is correct
40 Correct 1295 ms 176560 KB Output is correct
41 Correct 428 ms 111976 KB Output is correct
42 Correct 246 ms 21496 KB Output is correct
43 Correct 2396 ms 525920 KB Output is correct
44 Correct 2202 ms 525920 KB Output is correct
45 Correct 2117 ms 526000 KB Output is correct
46 Correct 940 ms 271588 KB Output is correct
47 Correct 1582 ms 220756 KB Output is correct
48 Correct 331 ms 22520 KB Output is correct
49 Correct 2320 ms 525900 KB Output is correct
50 Correct 2150 ms 525912 KB Output is correct
51 Correct 2416 ms 525724 KB Output is correct
52 Correct 1456 ms 220416 KB Output is correct
53 Correct 480 ms 136060 KB Output is correct