oj.uz

Submission #375055

# Submission time Handle Problem Language Result Execution time Memory
375055 2021-03-09T01:45:40 Z daniel920712 Examination (JOI19_examination) C++14
41 / 100
 1567 ms 443468 KB 
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>

using namespace std;
struct A
{
    int l,r;
    int nxl,nxr,nxt;
    int sum;
}Node[400*100005];
int ans[1000005];
vector < pair < pair < int , int > , int > > query[5][200005];
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,200000,-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 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);
        query[0][x].push_back(make_pair(make_pair(y,0),0));
    }
    for(i=0;i<M;i++)
    {
        scanf("%d %d %d",&x,&y,&z);
        query[1][x].push_back(make_pair(make_pair(y,z),i));
    }
    New(0,200000,-1,0);
    for(i=100000;i>=0;i--)
    {
        for(auto j:query[0][i]) cha(j.first.first,i+j.first.first,0);
        for(auto j:query[1][i]) ans[j.second]=Find(j.first.first,200000,j.first.second,200000,0);
    }
    for(i=0;i<M;i++) printf("%d\n",ans[i]);
    return 0;
}

Compilation message

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

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23916 KB Output is correct
2 Correct 17 ms 23916 KB Output is correct
3 Correct 17 ms 23916 KB Output is correct
4 Runtime error 93 ms 48000 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1374 ms 440428 KB Output is correct
2 Correct 1358 ms 441068 KB Output is correct
3 Correct 1314 ms 441376 KB Output is correct
4 Correct 423 ms 116716 KB Output is correct
5 Correct 717 ms 171476 KB Output is correct
6 Correct 282 ms 29532 KB Output is correct
7 Correct 1353 ms 441140 KB Output is correct
8 Correct 1389 ms 441476 KB Output is correct
9 Correct 1331 ms 440920 KB Output is correct
10 Correct 622 ms 157664 KB Output is correct
11 Correct 388 ms 100332 KB Output is correct
12 Correct 258 ms 28256 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1374 ms 440428 KB Output is correct
2 Correct 1358 ms 441068 KB Output is correct
3 Correct 1314 ms 441376 KB Output is correct
4 Correct 423 ms 116716 KB Output is correct
5 Correct 717 ms 171476 KB Output is correct
6 Correct 282 ms 29532 KB Output is correct
7 Correct 1353 ms 441140 KB Output is correct
8 Correct 1389 ms 441476 KB Output is correct
9 Correct 1331 ms 440920 KB Output is correct
10 Correct 622 ms 157664 KB Output is correct
11 Correct 388 ms 100332 KB Output is correct
12 Correct 258 ms 28256 KB Output is correct
13 Correct 1499 ms 441312 KB Output is correct
14 Correct 1461 ms 443396 KB Output is correct
15 Correct 1298 ms 442896 KB Output is correct
16 Correct 514 ms 117996 KB Output is correct
17 Correct 791 ms 172856 KB Output is correct
18 Correct 319 ms 29360 KB Output is correct
19 Correct 1475 ms 443372 KB Output is correct
20 Correct 1524 ms 443468 KB Output is correct
21 Correct 1567 ms 443244 KB Output is correct
22 Correct 641 ms 159072 KB Output is correct
23 Correct 377 ms 100844 KB Output is correct
24 Correct 257 ms 28384 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23916 KB Output is correct
2 Correct 17 ms 23916 KB Output is correct
3 Correct 17 ms 23916 KB Output is correct
4 Runtime error 93 ms 48000 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -