Submission #165908

#	Time	Username	Problem	Language	Result	Execution time	Memory
165908		Akashi	Examination (JOI19_examination)	C++14	0 / 100	606 ms	21116 KiB

examination

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

struct grades{
    int x, y, z;
    bool operator < (const grades &aux)const{
        if(z != aux.z) return z > aux.z;
        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;
    node *arb;
    node *left, *right;

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

node *arb;

int y, nx, ny, NR;
void update(int x, node *nod, int st, int dr){
    if(st == dr){
        if(nod->tip == 1){
            if(nod->arb == NULL) nod->arb = new node(0);
            update(y, nod->arb, 1, ny);
        }
        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, 1, ny);
    }
    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, int st, int dr){
    if(x <= st && dr <= y){
        if(nod->tip == 1){
            if(nod->arb == NULL) return 0;
            return query(yl, yr, nod->arb, 1, ny);
        }
        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;
}

set <int> sx, sy;
map <int, int> fx, fy;

int main()
{
    scanf("%d%d", &n, &q);
    for(int i = 1; i <= n ; ++i){
        scanf("%d%d", &a[i].x, &a[i].y);
        a[i].z = a[i].x + a[i].y;
        sx.insert(a[i].x); sy.insert(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;
        sx.insert(b[i].x); sy.insert(b[i].y);
    }

    for(auto it : sx) fx[it] = ++nx;
    for(auto it : sy) fy[it] = ++ny;

    NR = max(nx, ny);

    for(int i = 1; i <= n ; ++i) a[i].x = fx[a[i].x], a[i].y = fy[a[i].y];
    for(int i = 1; i <= q ; ++i) b[i].x = fx[b[i].x], b[i].y = fy[b[i].y];

    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].z >= b[i].z){
//            y = a[j].y;
//            update(a[j].x, arb, 1, nx);
//            ++j;
//        }
//
//        yl = b[i].y; yr = ny;
//        ans[b[i].p] = query(b[i].x, nx, arb, 1, nx);
//    }

    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:103: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:105: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:111: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: 0 / 2
• Subtask 2: 0 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57