oj.uz

Submission #152620

# Submission time Handle Problem Language Result Execution time Memory
152620 2019-09-08T15:27:08 Z arnold518 Examination (JOI19_examination) C++14
2 / 100
 3000 ms 609312 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)
{
    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]);
}

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)':
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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 3 ms 632 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 184 ms 85240 KB Output is correct
8 Correct 196 ms 85240 KB Output is correct
9 Correct 183 ms 85368 KB Output is correct
10 Correct 130 ms 58232 KB Output is correct
11 Correct 126 ms 59896 KB Output is correct
12 Correct 24 ms 504 KB Output is correct
13 Correct 184 ms 85280 KB Output is correct
14 Correct 184 ms 85428 KB Output is correct
15 Correct 183 ms 85356 KB Output is correct
16 Correct 121 ms 59136 KB Output is correct
17 Correct 127 ms 57340 KB Output is correct
18 Correct 20 ms 504 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3059 ms 609312 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 3059 ms 609312 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 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 3 ms 632 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 184 ms 85240 KB Output is correct
8 Correct 196 ms 85240 KB Output is correct
9 Correct 183 ms 85368 KB Output is correct
10 Correct 130 ms 58232 KB Output is correct
11 Correct 126 ms 59896 KB Output is correct
12 Correct 24 ms 504 KB Output is correct
13 Correct 184 ms 85280 KB Output is correct
14 Correct 184 ms 85428 KB Output is correct
15 Correct 183 ms 85356 KB Output is correct
16 Correct 121 ms 59136 KB Output is correct
17 Correct 127 ms 57340 KB Output is correct
18 Correct 20 ms 504 KB Output is correct
19 Execution timed out 3059 ms 609312 KB Time limit exceeded
20 Halted 0 ms 0 KB -