Submission #152625

#	Time	Username	Problem	Language	Result	Execution time	Memory
152625		arnold518	Examination (JOI19_examination)	C++14	100 / 100	2032 ms	275552 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];

vector<int> xcomp, ycomp;
int getxcomp(int x) { return lower_bound(xcomp.begin(), xcomp.end(), x)-xcomp.begin()+1; }
int getycomp(int y) { return lower_bound(ycomp.begin(), ycomp.end(), y)-ycomp.begin()+1; }

struct Node1
{
    int val; Node1 *lc, *rc;
    Node1() : val(0), 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++;
}

Node1 *tree[MAXN+10];
void update2(int y, int x) { for(; y<=ycomp.size(); y+=(y&-y)) update1(tree[y], 1, xcomp.size(), x); }
int query2(int y, int xl, int xr) { int ret=0; for(; y>0; y-=(y&-y)) ret+=query1(tree[y], 1, xcomp.size(), xl, xr); return ret; }
int query2(int yl, int yr, int xl, int xr) { return query2(yr, xl, xr)-query2(yl-1, xl, xr); }

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), xcomp.push_back(A[i].first), ycomp.push_back(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;

    xcomp.push_back(MAXVAL);
    ycomp.push_back(MAXVAL);
    for(i=0; i<=ycomp.size(); i++) tree[i]=new Node1();

    sort(xcomp.begin(), xcomp.end());
    sort(ycomp.begin(), ycomp.end());
    xcomp.erase(unique(xcomp.begin(), xcomp.end()), xcomp.end());
    ycomp.erase(unique(ycomp.begin(), ycomp.end()), ycomp.end());
    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; });

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

Compilation message (stderr)

examination.cpp: In function 'int query1(Node1*, int, int, int, int)':
examination.cpp:32:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
examination.cpp: In function 'void update1(Node1*, int, int, int)':
examination.cpp:46:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
examination.cpp: In function 'void update2(int, int)':
examination.cpp:61:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 void update2(int y, int x) { for(; y<=ycomp.size(); y+=(y&-y)) update1(tree[y], 1, xcomp.size(), x); }
                                    ~^~~~~~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:75:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<=ycomp.size(); i++) tree[i]=new Node1();
              ~^~~~~~~~~~~~~~
examination.cpp:67:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
examination.cpp:69: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:70:94: 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), xcomp.push_back(A[i].first), ycomp.push_back(A[i].second);
                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:71: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: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57