Submission #165900

#	Time	Username	Problem	Language	Result	Execution time	Memory
165900		Akashi	Examination (JOI19_examination)	C++14	2 / 100	3089 ms	708332 KiB

examination

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

struct grades{
    int x, y;
    bool operator < (const grades &aux)const{
        if(x + y != aux.x + aux.y) return x + y > aux.x + aux.y;
        if(x != aux.x) return x > aux.x;
        return y > aux.y;
    }
};
struct teacher{
    int x, y, z, p;
    bool operator < (const teacher &aux)const{
        if(z != aux.z) return z > aux.z;
        if(x != aux.x) return x > aux.x;
        return y > aux.y;
    }
};

grades a[100005];
teacher b[100005];
int ans[100005];

int n, q;

struct node{
    int tip, val = 0;
    node *arb;
    node *left, *right;

    node(bool x){
        tip = x;
        val = 0;
        arb = left = right = NULL;
    }
};

node *arb;

int y;
void update(int x, node *nod = arb, int st = 0, int dr = 1e9){
    if(st == dr){
        if(nod->tip == 1){
            if(nod->arb == NULL) nod->arb = new node(0);
            update(y, nod->arb);
        }
        else ++nod->val;
        return ;
    }

    int mij = (st + dr) / 2;
    if(x <= mij){
        if(nod->left == NULL) nod->left = new node(nod->tip);
        update(x, nod->left, st, mij);
    }
    else{
        if(nod->right == NULL) nod->right = new node(nod->tip);
        update(x, nod->right, mij + 1, dr);
    }


    if(nod->tip == 1){
        if(nod->arb == NULL) nod->arb = new node(0);
        update(y, nod->arb);
    }
    else{
        nod->val = 0;
        if(nod->left != NULL) nod->val += nod->left->val;
        if(nod->right!= NULL) nod->val += nod->right->val;
    }
}

int yr, yl;
int query(int x, int y, node *nod = arb, int st = 0, int dr = 1e9){
    if(x <= st && dr <= y){
        if(nod->tip == 1){
            if(nod->arb == NULL) return 0;
            return query(yl, yr, nod->arb);
        }
        else return nod->val;
    }

    int mij = (st + dr) / 2;

    int val = 0;
    if(x <= mij){
        if(nod->left != NULL) val += query(x, y, nod->left, st, mij);
    }
    if(mij + 1 <= y){
        if(nod->right != NULL) val += query(x, y, nod->right, mij + 1, dr);
    }

    return val;
}

int main()
{
    scanf("%d%d", &n, &q);
    for(int i = 1; i <= n ; ++i)
        scanf("%d%d", &a[i].x, &a[i].y);

    for(int i = 1; i <= q ; ++i)
        scanf("%d%d%d", &b[i].x, &b[i].y, &b[i].z), b[i].p = i;

    sort(a + 1, a + n + 1);
    sort(b + 1, b + q + 1);

    int j = 1;
    arb = new node(1);
    for(int i = 1; i <= q ; ++i){
        while(j <= n && a[j].x + a[j].y >= b[i].z){
            y = a[j].y;
            update(a[j].x);
            ++j;
        }

        yl = b[i].y; yr = INF;
        ans[b[i].p] = query(b[i].x, INF);
    }

    for(int i = 1; i <= q ; ++i) printf("%d\n", ans[i]);

    return 0;
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:102: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:104:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a[i].x, &a[i].y);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:107:51: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &b[i].x, &b[i].y, &b[i].z), b[i].p = i;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

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