Submission #166028

#	Time	Username	Problem	Language	Result	Execution time	Memory
166028		Akashi	Examination (JOI19_examination)	C++14	2 / 100	1033 ms	144504 KiB

examination

#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;
    int left, right;
};

node Tree[8000005];

int y, nx, ny, NR;
void update(int x, int nod, int st, int dr){
    if(st == dr){
        if(Tree[nod].tip == 1){
            if(Tree[nod].val == 0){
                Tree[nod].val = ++NR;
                Tree[NR].tip = 0;
            }
            update(y, Tree[nod].val, 1, ny);
        }
        else ++Tree[nod].val;
        return ;
    }

    int mij = (st + dr) / 2;
    if(x <= mij){
        if(Tree[nod].left == 0){
            Tree[nod].left = ++NR;
            Tree[NR].tip = Tree[nod].tip;
        }
        update(x, Tree[nod].left, st, mij);
    }
    else{
        if(Tree[nod].right == 0){
            Tree[nod].right = ++NR;
            Tree[NR].tip = Tree[nod].tip;
        }
        update(x, Tree[nod].right, mij + 1, dr);
    }

    if(Tree[nod].tip == 1){
        if(Tree[nod].val == 0){
            Tree[nod].val = ++NR;
            Tree[NR].tip = 0;
        }
        update(y, Tree[nod].val, 1, ny);
    }
    else Tree[nod].val = Tree[Tree[nod].left].val + Tree[Tree[nod].right].val;

}

int yr, yl;
int query(int x, int y, int nod, int st, int dr){
    if(x <= st && dr <= y){
        if(Tree[nod].tip == 1){
            if(Tree[nod].val == 0) return 0;
            return query(yl, yr, Tree[nod].val, 1, ny);
        }
        else return Tree[nod].val;
    }

    int mij = (st + dr) / 2;

    int val = 0;
    if(x <= mij){
        if(Tree[nod].left) val += query(x, y, Tree[nod].left, st, mij);
    }
    if(mij + 1 <= y){
        if(Tree[nod].right) val += query(x, y, Tree[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;

    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;
    Tree[++NR].tip = 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, 1, 1, nx);
            ++j;
        }

        yl = b[i].y; yr = ny;
        ans[b[i].p] = query(b[i].x, nx, 1, 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: 2 / 2
• Subtask 2: 0 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57