oj.uz

Submission #152610

# Submission time Handle Problem Language Result Execution time Memory
152610 2019-09-08T15:01:36 Z arnold518 Examination (JOI19_examination) C++14
0 / 100
 3000 ms 408668 KB 
#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, int val)
{
    if(tl==tr)
    {
        node->val+=val;
        return;
    }
    int mid=tl+tr>>1;
    if(x<=mid)
    {
        if(node->lc==NULL) node->lc=new Node1();
        update1(node->lc, tl, mid, x, val);
    }
    else
    {
        if(node->rc==NULL) node->rc=new Node1();
        update1(node->rc, mid+1, tr, x, val);
    }
    int t=0;
    if(node->lc!=NULL) t+=node->lc->val;
    if(node->rc!=NULL) t+=node->rc->val;
    node->val=t;
}

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, int val)
{
    if(node->val==NULL) node->val=new Node1();
    if(tl==tr)
    {
        update1(node->val, 0, MAXVAL, x, val);
        return;
    }
    int mid=tl+tr>>1;
    if(y<=mid)
    {
        if(node->lc==NULL) node->lc=new Node2();
        update2(node->lc, tl, mid, y, x, val);
    }
    else
    {
        if(node->rc==NULL) node->rc=new Node2();
        update2(node->rc, mid+1, tr, y, x, val);
    }
    int t=0;
    if(node->lc!=NULL) t+=query1(node->lc->val, 0, MAXVAL, x, x);
    if(node->rc!=NULL) t+=query1(node->rc->val, 0, MAXVAL, x, x);
    update1(node->val, 0, MAXVAL, x, t);
}

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, 1);
        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]);
}

Compilation message

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, 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:73:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
examination.cpp: In function 'void update2(Node2*, int, int, int, int, int)':
examination.cpp:88:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
examination.cpp: In function 'int main()':
examination.cpp:109:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
examination.cpp:111: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:112: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:113: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
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Incorrect 2 ms 504 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3040 ms 408668 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3040 ms 408668 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Incorrect 2 ms 504 KB Output isn't correct
3 Halted 0 ms 0 KB -