Submission #375053

#	Time	Username	Problem	Language	Result	Execution time	Memory
375053		daniel920712	Examination (JOI19_examination)	C++14	20 / 100	198 ms	35948 KiB

examination

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>

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

Compilation message (stderr)

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

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