제출 #375059

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
375059		daniel920712	Examination (JOI19_examination)	C++14	100 / 100	1925 ms	537948 KiB

examination

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57