oj.uz

Submission #375059

# Submission time Handle Problem Language Result Execution time Memory
375059 2021-03-09T01:55:06 Z daniel920712 Examination (JOI19_examination) C++14
100 / 100
 1925 ms 537948 KB 
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>

using namespace std;
struct A
{
    int l,r;
    int nxl,nxr,nxt;
    int sum;
}Node[400*100005];
int ans[1000005];
int XX[300005];
int YY[300005];
vector < pair < pair < int , int > , int > > query[5][300005];
vector < int > all;

int now=1;
void New(int l,int r,int t,int here)
{
    Node[here].l=l;
    Node[here].r=r;
    Node[here].sum=0;
    Node[here].nxl=-1;
    Node[here].nxr=-1;
    Node[here].nxt=t;
}
void cha(int x,int y,int here)
{
    Node[here].sum++;
    if(Node[here].nxt==-2)
    {
        if(y==Node[here].l&&y==Node[here].r) return;
        if(y<=(Node[here].l+Node[here].r)/2)
        {
            if(Node[here].nxl==-1)
            {
                Node[here].nxl=now++;
                New(Node[here].l,(Node[here].l+Node[here].r)/2,-2,Node[here].nxl);
            }
            cha(x,y,Node[here].nxl);
        }
        else
        {
            if(Node[here].nxr==-1)
            {
                Node[here].nxr=now++;
                New((Node[here].l+Node[here].r)/2+1,Node[here].r,-2,Node[here].nxr);
            }
            cha(x,y,Node[here].nxr);
        }
    }
    else
    {
        if(Node[here].nxt==-1)
        {
            Node[here].nxt=now++;
            New(0,300000,-2,Node[here].nxt);
        }
        cha(x,y,Node[here].nxt);
        if(x==Node[here].l&&x==Node[here].r) return;
        else if(x<=(Node[here].l+Node[here].r)/2)
        {
            if(Node[here].nxl==-1)
            {
                Node[here].nxl=now++;
                New(Node[here].l,(Node[here].l+Node[here].r)/2,-1,Node[here].nxl);
            }
            cha(x,y,Node[here].nxl);
        }
        else
        {
            if(Node[here].nxr==-1)
            {
                Node[here].nxr=now++;
                New((Node[here].l+Node[here].r)/2+1,Node[here].r,-1,Node[here].nxr);
            }
            cha(x,y,Node[here].nxr);
        }
    }

}
int Find(int l1,int r1,int l2,int r2,int here)
{
    if(here==-1) return 0;
    if(Node[here].nxt==-2)
    {
        if(l2==Node[here].l&&r2==Node[here].r) return Node[here].sum;
        if(r2<=(Node[here].l+Node[here].r)/2) return Find(l1,r1,l2,r2,Node[here].nxl);
        else if(l2>(Node[here].l+Node[here].r)/2) return Find(l1,r1,l2,r2,Node[here].nxr);
        else return Find(l1,r1,l2,(Node[here].l+Node[here].r)/2,Node[here].nxl)+Find(l1,r1,(Node[here].l+Node[here].r)/2+1,r2,Node[here].nxr);
    }
    else
    {
        if(l1==Node[here].l&&r1==Node[here].r) return Find(l1,r1,l2,r2,Node[here].nxt);
        if(r1<=(Node[here].l+Node[here].r)/2) return Find(l1,r1,l2,r2,Node[here].nxl);
        else if(l1>(Node[here].l+Node[here].r)/2) return Find(l1,r1,l2,r2,Node[here].nxr);
        else return Find(l1,(Node[here].l+Node[here].r)/2,l2,r2,Node[here].nxl)+Find((Node[here].l+Node[here].r)/2+1,r1,l2,r2,Node[here].nxr);
    }

}
int Cha(int x)
{
    return lower_bound(all.begin(),all.end(),x)-all.begin();
}
int main()
{
    int N,M,i,j,x,y,z;
    scanf("%d %d",&N,&M);
    for(i=0;i<N;i++)
    {
        scanf("%d %d",&x,&y);
        all.push_back(x);
        all.push_back(y);
        all.push_back(x+y);
        XX[i]=x;
        YY[i]=y;
        //query[0][x].push_back(make_pair(make_pair(y,0),0));
    }
    sort(all.begin(),all.end());
    for(i=0;i<N;i++)
    {
        query[0][Cha(XX[i])].push_back(make_pair(make_pair(Cha(YY[i]),Cha(XX[i]+YY[i])),0));
    }
    for(i=0;i<M;i++)
    {
        scanf("%d %d %d",&x,&y,&z);
        query[1][Cha(x)].push_back(make_pair(make_pair(Cha(y),Cha(z)),i));
        //query[1][x].push_back(make_pair(make_pair(y,z),i));
    }
    New(0,300000,-1,0);
    for(i=300000;i>=0;i--)
    {
        for(auto j:query[0][i]) cha(j.first.first,j.first.second,0);
        for(auto j:query[1][i]) ans[j.second]=Find(j.first.first,300000,j.first.second,300000,0);
    }
    for(i=0;i<M;i++) printf("%d\n",ans[i]);
    return 0;
}

Compilation message

examination.cpp: In function 'int main()':
examination.cpp:110:15: warning: unused variable 'j' [-Wunused-variable]
  110 |     int N,M,i,j,x,y,z;
      |               ^
examination.cpp:111:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  111 |     scanf("%d %d",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~
examination.cpp:114:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  114 |         scanf("%d %d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~~
examination.cpp:129:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  129 |         scanf("%d %d %d",&x,&y,&z);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 35584 KB Output is correct
2 Correct 26 ms 35564 KB Output is correct
3 Correct 26 ms 35564 KB Output is correct
4 Correct 26 ms 35564 KB Output is correct
5 Correct 26 ms 35564 KB Output is correct
6 Correct 25 ms 35564 KB Output is correct
7 Correct 54 ms 46316 KB Output is correct
8 Correct 54 ms 46316 KB Output is correct
9 Correct 54 ms 46316 KB Output is correct
10 Correct 45 ms 41964 KB Output is correct
11 Correct 48 ms 43520 KB Output is correct
12 Correct 39 ms 36204 KB Output is correct
13 Correct 51 ms 46316 KB Output is correct
14 Correct 50 ms 46316 KB Output is correct
15 Correct 50 ms 46444 KB Output is correct
16 Correct 43 ms 43372 KB Output is correct
17 Correct 40 ms 40044 KB Output is correct
18 Correct 33 ms 35820 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1548 ms 522348 KB Output is correct
2 Correct 1522 ms 522328 KB Output is correct
3 Correct 1539 ms 522844 KB Output is correct
4 Correct 710 ms 271556 KB Output is correct
5 Correct 938 ms 243984 KB Output is correct
6 Correct 345 ms 43288 KB Output is correct
7 Correct 1485 ms 522692 KB Output is correct
8 Correct 1478 ms 523052 KB Output is correct
9 Correct 1412 ms 522856 KB Output is correct
10 Correct 819 ms 226128 KB Output is correct
11 Correct 549 ms 147500 KB Output is correct
12 Correct 305 ms 41948 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1548 ms 522348 KB Output is correct
2 Correct 1522 ms 522328 KB Output is correct
3 Correct 1539 ms 522844 KB Output is correct
4 Correct 710 ms 271556 KB Output is correct
5 Correct 938 ms 243984 KB Output is correct
6 Correct 345 ms 43288 KB Output is correct
7 Correct 1485 ms 522692 KB Output is correct
8 Correct 1478 ms 523052 KB Output is correct
9 Correct 1412 ms 522856 KB Output is correct
10 Correct 819 ms 226128 KB Output is correct
11 Correct 549 ms 147500 KB Output is correct
12 Correct 305 ms 41948 KB Output is correct
13 Correct 1694 ms 522868 KB Output is correct
14 Correct 1669 ms 522588 KB Output is correct
15 Correct 1496 ms 522316 KB Output is correct
16 Correct 816 ms 269788 KB Output is correct
17 Correct 1047 ms 244020 KB Output is correct
18 Correct 351 ms 43100 KB Output is correct
19 Correct 1724 ms 522344 KB Output is correct
20 Correct 1785 ms 522484 KB Output is correct
21 Correct 1867 ms 522816 KB Output is correct
22 Correct 793 ms 226652 KB Output is correct
23 Correct 518 ms 147292 KB Output is correct
24 Correct 317 ms 42460 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 35584 KB Output is correct
2 Correct 26 ms 35564 KB Output is correct
3 Correct 26 ms 35564 KB Output is correct
4 Correct 26 ms 35564 KB Output is correct
5 Correct 26 ms 35564 KB Output is correct
6 Correct 25 ms 35564 KB Output is correct
7 Correct 54 ms 46316 KB Output is correct
8 Correct 54 ms 46316 KB Output is correct
9 Correct 54 ms 46316 KB Output is correct
10 Correct 45 ms 41964 KB Output is correct
11 Correct 48 ms 43520 KB Output is correct
12 Correct 39 ms 36204 KB Output is correct
13 Correct 51 ms 46316 KB Output is correct
14 Correct 50 ms 46316 KB Output is correct
15 Correct 50 ms 46444 KB Output is correct
16 Correct 43 ms 43372 KB Output is correct
17 Correct 40 ms 40044 KB Output is correct
18 Correct 33 ms 35820 KB Output is correct
19 Correct 1548 ms 522348 KB Output is correct
20 Correct 1522 ms 522328 KB Output is correct
21 Correct 1539 ms 522844 KB Output is correct
22 Correct 710 ms 271556 KB Output is correct
23 Correct 938 ms 243984 KB Output is correct
24 Correct 345 ms 43288 KB Output is correct
25 Correct 1485 ms 522692 KB Output is correct
26 Correct 1478 ms 523052 KB Output is correct
27 Correct 1412 ms 522856 KB Output is correct
28 Correct 819 ms 226128 KB Output is correct
29 Correct 549 ms 147500 KB Output is correct
30 Correct 305 ms 41948 KB Output is correct
31 Correct 1694 ms 522868 KB Output is correct
32 Correct 1669 ms 522588 KB Output is correct
33 Correct 1496 ms 522316 KB Output is correct
34 Correct 816 ms 269788 KB Output is correct
35 Correct 1047 ms 244020 KB Output is correct
36 Correct 351 ms 43100 KB Output is correct
37 Correct 1724 ms 522344 KB Output is correct
38 Correct 1785 ms 522484 KB Output is correct
39 Correct 1867 ms 522816 KB Output is correct
40 Correct 793 ms 226652 KB Output is correct
41 Correct 518 ms 147292 KB Output is correct
42 Correct 317 ms 42460 KB Output is correct
43 Correct 1777 ms 537948 KB Output is correct
44 Correct 1765 ms 537864 KB Output is correct
45 Correct 1717 ms 537384 KB Output is correct
46 Correct 828 ms 284636 KB Output is correct
47 Correct 1012 ms 300252 KB Output is correct
48 Correct 358 ms 43996 KB Output is correct
49 Correct 1767 ms 536796 KB Output is correct
50 Correct 1725 ms 537436 KB Output is correct
51 Correct 1925 ms 536668 KB Output is correct
52 Correct 949 ms 297688 KB Output is correct
53 Correct 552 ms 187032 KB Output is correct