oj.uz

Submission #166033

# Submission time Handle Problem Language Result Execution time Memory
166033 2019-11-30T09:44:02 Z Akashi Examination (JOI19_examination) C++14
0 / 100
 2 ms 376 KB 
#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[32000005];

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()
{
    freopen("02-01.txt", "r", stdin);
    freopen("02-01.out", "w", stdout);
    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);
    }

//    nx = 200000; ny = 200000;
//    srand(time(NULL));
//    for(int i = 1; i <= 100000 ; ++i){
//        y = rand() % (200000) + 1;
//        int x = rand() % (200000) + 1;
//        update(x, 1, 1, nx);
//        if(i % 1000 == 0) cerr << NR << endl;
//    }
//

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

    return 0;
}

Compilation message

examination.cpp: In function 'int main()':
examination.cpp:103:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("02-01.txt", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:104:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("02-01.out", "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
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:107: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:113: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.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 57.0

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