oj.uz

Submission #102484

# Submission time Handle Problem Language Result Execution time Memory
102484 2019-03-25T09:40:56 Z FutymyClone Examination (JOI19_examination) C++14
2 / 100
 3000 ms 230368 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int n, q, ans[N], cnt = 0;
map <int, int> bit[N], compress;
vector <int> vecm, veci;

struct data {
    int math, infor, sum;
    bool operator < (const data &rhs) const {
        return sum > rhs.sum;
    }
} a[N];

struct Query {
    int a, b, c, id;
    bool operator < (const Query &rhs) const {
        return c > rhs.c;
    }
} queries[N];

void update (int x, int y, int val) {
    for (int i = x; i > 0; i -= i & -i) {
        for (int j = y; j > 0; j -= j & -j) {
            bit[i][j] += val;
        }
    }
}

int get_value (int x, int y) {
    int ans = 0;
    for (int i = x; i < N; i += i & -i) {
        for (int j = y; j < N; j += j & -j) {
            ans += bit[i][j];
        }
    }

    return ans;
}

int main(){
    scanf("%d %d", &n, &q);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &a[i].math, &a[i].infor);
        a[i].sum = a[i].math + a[i].infor;
        vecm.push_back(a[i].math);
        veci.push_back(a[i].infor);
    }

    for (int i = 1; i <= q; i++) {
        scanf("%d %d %d", &queries[i].a, &queries[i].b, &queries[i].c);
        queries[i].id = i;
        vecm.push_back(queries[i].a);
        veci.push_back(queries[i].b);
    }

    sort(a + 1, a + n + 1);
    sort(queries + 1, queries + q + 1);
    sort(vecm.begin(), vecm.end());
    sort(veci.begin(), veci.end());

    //Compress coordinate
    compress[vecm[0]] = ++cnt;
    for (int i = 1; i < vecm.size(); i++) if (vecm[i] > vecm[i - 1]) compress[vecm[i]] = ++cnt;
    for (int i = 1; i <= n; i++) a[i].math = compress[a[i].math];
    for (int i = 1; i <= q; i++) queries[i].a = compress[queries[i].a];

    cnt = 0; compress.clear();
    compress[veci[0]] = ++cnt;
    for (int i = 1; i < veci.size(); i++) if (veci[i] > veci[i - 1]) compress[veci[i]] = ++cnt;
    for (int i = 1; i <= n; i++) a[i].infor = compress[a[i].infor];
    for (int i = 1; i <= q; i++) queries[i].b = compress[queries[i].b];
    //

    int ptr = 1;
    for (int i = 1; i <= q; i++) {
        while (ptr <= n && a[ptr].sum >= queries[i].c) {
            update(a[ptr].math, a[ptr].infor, 1);
            ptr++;
        }

        ans[queries[i].id] = get_value(queries[i].a, queries[i].b);
    }

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

Compilation message

examination.cpp: In function 'int main()':
examination.cpp:67:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < vecm.size(); i++) if (vecm[i] > vecm[i - 1]) compress[vecm[i]] = ++cnt;
                     ~~^~~~~~~~~~~~~
examination.cpp:73:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < veci.size(); i++) if (veci[i] > veci[i - 1]) compress[veci[i]] = ++cnt;
                     ~~^~~~~~~~~~~~~
examination.cpp:45: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:47:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a[i].math, &a[i].infor);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &queries[i].a, &queries[i].b, &queries[i].c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5100 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 6 ms 4992 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 8 ms 4992 KB Output is correct
6 Correct 7 ms 4992 KB Output is correct
7 Correct 101 ms 14424 KB Output is correct
8 Correct 106 ms 14200 KB Output is correct
9 Correct 100 ms 14236 KB Output is correct
10 Correct 34 ms 8824 KB Output is correct
11 Correct 65 ms 9140 KB Output is correct
12 Correct 15 ms 5248 KB Output is correct
13 Correct 96 ms 14384 KB Output is correct
14 Correct 113 ms 14200 KB Output is correct
15 Correct 96 ms 14120 KB Output is correct
16 Correct 54 ms 8840 KB Output is correct
17 Correct 33 ms 8648 KB Output is correct
18 Correct 18 ms 5248 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3101 ms 230368 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 3101 ms 230368 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5100 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 6 ms 4992 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 8 ms 4992 KB Output is correct
6 Correct 7 ms 4992 KB Output is correct
7 Correct 101 ms 14424 KB Output is correct
8 Correct 106 ms 14200 KB Output is correct
9 Correct 100 ms 14236 KB Output is correct
10 Correct 34 ms 8824 KB Output is correct
11 Correct 65 ms 9140 KB Output is correct
12 Correct 15 ms 5248 KB Output is correct
13 Correct 96 ms 14384 KB Output is correct
14 Correct 113 ms 14200 KB Output is correct
15 Correct 96 ms 14120 KB Output is correct
16 Correct 54 ms 8840 KB Output is correct
17 Correct 33 ms 8648 KB Output is correct
18 Correct 18 ms 5248 KB Output is correct
19 Execution timed out 3101 ms 230368 KB Time limit exceeded
20 Halted 0 ms 0 KB -