제출 #152620

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
152620		arnold518	Examination (JOI19_examination)	C++14	2 / 100	3059 ms	609312 KiB

examination

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;
const int MAXQ = 1e5;
const int MAXVAL = 1e9;

int N, Q, ans[MAXQ+10];
pii A[MAXN+10];

struct Data { int x, y, z, num; };
Data B[MAXQ+10];

struct Node1
{
    int val; Node1 *lc, *rc;
    Node1() : val(0), lc(NULL), rc(NULL) {}
};

struct Node2
{
    Node1 *val; Node2 *lc, *rc;
    Node2() : val(NULL), lc(NULL), rc(NULL) {}
};

int query1(Node1 *node, int tl, int tr, int xl, int xr)
{
    if(xr<tl || tr<xl) return 0;
    if(xl<=tl && tr<=xr) return node->val;
    int mid=tl+tr>>1;
    int ret=0;
    if(node->lc!=NULL) ret+=query1(node->lc, tl, mid, xl, xr);
    if(node->rc!=NULL) ret+=query1(node->rc, mid+1, tr, xl, xr);
    return ret;
}

void update1(Node1 *node, int tl, int tr, int x)
{
    if(tl==tr)
    {
        node->val++;
        return;
    }
    int mid=tl+tr>>1;
    if(x<=mid)
    {
        if(node->lc==NULL) node->lc=new Node1();
        update1(node->lc, tl, mid, x);
    }
    else
    {
        if(node->rc==NULL) node->rc=new Node1();
        update1(node->rc, mid+1, tr, x);
    }
    node->val++;
}

int query2(Node2 *node, int tl, int tr, int yl, int yr, int xl, int xr)
{
    if(tr<yl || yr<tl) return 0;
    if(yl<=tl && tr<=yr)
    {
        if(node->val!=NULL) return query1(node->val, 0, MAXVAL, xl, xr);
        else return 0;
    }
    int mid=tl+tr>>1;
    int ret=0;
    if(node->lc!=NULL) ret+=query2(node->lc, tl, mid, yl, yr, xl, xr);
    if(node->rc!=NULL) ret+=query2(node->rc, mid+1, tr, yl, yr, xl, xr);
    return ret;
}

void update2(Node2 *node, int tl, int tr, int y, int x)
{
    if(node->val==NULL) node->val=new Node1();
    if(tl==tr)
    {
        update1(node->val, 0, MAXVAL, x);
        return;
    }
    int mid=tl+tr>>1;
    if(y<=mid)
    {
        if(node->lc==NULL) node->lc=new Node2();
        update2(node->lc, tl, mid, y, x);
    }
    else
    {
        if(node->rc==NULL) node->rc=new Node2();
        update2(node->rc, mid+1, tr, y, x);
    }
    update1(node->val, 0, MAXVAL, x);
}

Node2 *root;

int main()
{
    int i, j;

    scanf("%d%d", &N, &Q);
    for(i=1; i<=N; i++) scanf("%d%d", &A[i].first, &A[i].second);
    for(i=1; i<=Q; i++) scanf("%d%d%d", &B[i].x, &B[i].y, &B[i].z), B[i].num=i;

    sort(A+1, A+N+1, [&](const pii &p, const pii &q) { return p.first+p.second>q.first+q.second; });
    sort(B+1, B+Q+1, [&](const Data &p, const Data &q) { return p.z>q.z; });

    root=new Node2();

    int it=1;
    for(i=1; i<=Q; i++)
    {
        for(; it<=N && A[it].first+A[it].second>=B[i].z; it++) update2(root, 0, MAXVAL, A[it].second, A[it].first);
        ans[B[i].num]=query2(root, 0, MAXVAL, B[i].y, MAXVAL, B[i].x, MAXVAL);
    }
    for(i=1; i<=Q; i++) printf("%d\n", ans[i]);
}

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

examination.cpp: In function 'int query1(Node1*, int, int, int, int)':
examination.cpp:34:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
examination.cpp: In function 'void update1(Node1*, int, int, int)':
examination.cpp:48:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
examination.cpp: In function 'int query2(Node2*, int, int, int, int, int, int)':
examination.cpp:70:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
examination.cpp: In function 'void update2(Node2*, int, int, int, int)':
examination.cpp:85:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
examination.cpp: In function 'int main()':
examination.cpp:103:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
examination.cpp:105:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &Q);
     ~~~~~^~~~~~~~~~~~~~~~
examination.cpp:106:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1; i<=N; i++) scanf("%d%d", &A[i].first, &A[i].second);
                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:107:67: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1; i<=Q; i++) scanf("%d%d%d", &B[i].x, &B[i].y, &B[i].z), B[i].num=i;
                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

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