oj.uz

Submission #551962

# Submission time Handle Problem Language Result Execution time Memory
551962 2022-04-22T03:45:22 Z wenqi Examination (JOI19_examination) C++17
100 / 100
 2207 ms 676552 KB 
// trans rights

#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using ull = unsigned long long;

#ifdef DEBUG
#define D(...) fprintf(stderr, __VA_ARGS__)
#else
#define D(...)
#endif

int N, Q;
int answers[100069];
using ordered_set = tree<int, null_type, greater_equal<int>, rb_tree_tag, tree_order_statistics_node_update>;

struct Node
{
    int l, r;
    Node *lc, *rc;
    ordered_set bkt;
    Node(int l, int r) : l(l), r(r), lc(0), rc(0), bkt{} {}
    void clean()
    {
        if (l != r and not lc)
        {
            int m = l + (r - l) / 2;
            lc = new Node(l, m);
            rc = new Node(m + 1, r);
        }
    }
    void update(int a, int b)
    {
        bkt.insert(a + b);
        if (l == r)
            return;

        clean();
        if (b <= lc->r)
            lc->update(a, b);
        else
            rc->update(a, b);
    }
    int query(int x, int y, int z)
    {
        if (y > r)
            return 0;

        if (y <= l)
            return bkt.order_of_key(z - 1);

        clean();
        return lc->query(x, y, z) + rc->query(x, y, z);
    }
};

int main(int argc, const char *argv[])
{
    vector<pair<int, int>> students;
    vector<tuple<int, int, int, int>> queries;
    scanf("%d%d", &N, &Q);
    for (int i = 0; i < N; i++)
    {
        int s, t;
        scanf("%d%d", &s, &t);
        students.push_back({s, t});
    }
    for (int i = 0; i < Q; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        queries.push_back({x, y, z, i});
    }
    sort(students.begin(), students.end(), greater<>());
    sort(queries.begin(), queries.end(), greater<>());
    Node *root = new Node(0, 1e9);
    int ptr = 0;
    for (auto q : queries)
    {
        auto [x, y, z, i] = q;
        D("Q: %d %d %d\n", x, y, z);
        while (ptr < students.size() and students[ptr].first >= x)
        {
            auto [a, b] = students[ptr];
            D("S: %d %d\n", a, b);
            root->update(a, b);
            ptr++;
        }

        answers[i] = root->query(x, y, z);
    }
    for (int i = 0; i < Q; i++)
        printf("%d\n", answers[i]);
    return 0;
}

Compilation message

examination.cpp: In function 'int main(int, const char**)':
examination.cpp:85:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         while (ptr < students.size() and students[ptr].first >= x)
      |                ~~~~^~~~~~~~~~~~~~~~~
examination.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |     scanf("%d%d", &N, &Q);
      |     ~~~~~^~~~~~~~~~~~~~~~
examination.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         scanf("%d%d", &s, &t);
      |         ~~~~~^~~~~~~~~~~~~~~~
examination.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         scanf("%d%d%d", &x, &y, &z);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 32 ms 27092 KB Output is correct
8 Correct 32 ms 27056 KB Output is correct
9 Correct 36 ms 27096 KB Output is correct
10 Correct 21 ms 4692 KB Output is correct
11 Correct 28 ms 27076 KB Output is correct
12 Correct 17 ms 4724 KB Output is correct
13 Correct 33 ms 27084 KB Output is correct
14 Correct 37 ms 27160 KB Output is correct
15 Correct 33 ms 27140 KB Output is correct
16 Correct 29 ms 27084 KB Output is correct
17 Correct 19 ms 4764 KB Output is correct
18 Correct 22 ms 4692 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1784 ms 170276 KB Output is correct
2 Correct 1754 ms 170276 KB Output is correct
3 Correct 1731 ms 170248 KB Output is correct
4 Correct 942 ms 149312 KB Output is correct
5 Correct 775 ms 170400 KB Output is correct
6 Correct 842 ms 149252 KB Output is correct
7 Correct 1758 ms 172740 KB Output is correct
8 Correct 1602 ms 171852 KB Output is correct
9 Correct 1555 ms 171668 KB Output is correct
10 Correct 746 ms 171820 KB Output is correct
11 Correct 1404 ms 150876 KB Output is correct
12 Correct 1404 ms 150076 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1784 ms 170276 KB Output is correct
2 Correct 1754 ms 170276 KB Output is correct
3 Correct 1731 ms 170248 KB Output is correct
4 Correct 942 ms 149312 KB Output is correct
5 Correct 775 ms 170400 KB Output is correct
6 Correct 842 ms 149252 KB Output is correct
7 Correct 1758 ms 172740 KB Output is correct
8 Correct 1602 ms 171852 KB Output is correct
9 Correct 1555 ms 171668 KB Output is correct
10 Correct 746 ms 171820 KB Output is correct
11 Correct 1404 ms 150876 KB Output is correct
12 Correct 1404 ms 150076 KB Output is correct
13 Correct 1654 ms 173220 KB Output is correct
14 Correct 1660 ms 173128 KB Output is correct
15 Correct 1618 ms 172776 KB Output is correct
16 Correct 965 ms 151360 KB Output is correct
17 Correct 769 ms 172580 KB Output is correct
18 Correct 812 ms 150280 KB Output is correct
19 Correct 1659 ms 173144 KB Output is correct
20 Correct 1692 ms 173256 KB Output is correct
21 Correct 1720 ms 172948 KB Output is correct
22 Correct 744 ms 171920 KB Output is correct
23 Correct 1426 ms 150748 KB Output is correct
24 Correct 1410 ms 149824 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 32 ms 27092 KB Output is correct
8 Correct 32 ms 27056 KB Output is correct
9 Correct 36 ms 27096 KB Output is correct
10 Correct 21 ms 4692 KB Output is correct
11 Correct 28 ms 27076 KB Output is correct
12 Correct 17 ms 4724 KB Output is correct
13 Correct 33 ms 27084 KB Output is correct
14 Correct 37 ms 27160 KB Output is correct
15 Correct 33 ms 27140 KB Output is correct
16 Correct 29 ms 27084 KB Output is correct
17 Correct 19 ms 4764 KB Output is correct
18 Correct 22 ms 4692 KB Output is correct
19 Correct 1784 ms 170276 KB Output is correct
20 Correct 1754 ms 170276 KB Output is correct
21 Correct 1731 ms 170248 KB Output is correct
22 Correct 942 ms 149312 KB Output is correct
23 Correct 775 ms 170400 KB Output is correct
24 Correct 842 ms 149252 KB Output is correct
25 Correct 1758 ms 172740 KB Output is correct
26 Correct 1602 ms 171852 KB Output is correct
27 Correct 1555 ms 171668 KB Output is correct
28 Correct 746 ms 171820 KB Output is correct
29 Correct 1404 ms 150876 KB Output is correct
30 Correct 1404 ms 150076 KB Output is correct
31 Correct 1654 ms 173220 KB Output is correct
32 Correct 1660 ms 173128 KB Output is correct
33 Correct 1618 ms 172776 KB Output is correct
34 Correct 965 ms 151360 KB Output is correct
35 Correct 769 ms 172580 KB Output is correct
36 Correct 812 ms 150280 KB Output is correct
37 Correct 1659 ms 173144 KB Output is correct
38 Correct 1692 ms 173256 KB Output is correct
39 Correct 1720 ms 172948 KB Output is correct
40 Correct 744 ms 171920 KB Output is correct
41 Correct 1426 ms 150748 KB Output is correct
42 Correct 1410 ms 149824 KB Output is correct
43 Correct 2207 ms 676244 KB Output is correct
44 Correct 2131 ms 676552 KB Output is correct
45 Correct 2013 ms 676320 KB Output is correct
46 Correct 1538 ms 152500 KB Output is correct
47 Correct 1027 ms 675440 KB Output is correct
48 Correct 808 ms 150060 KB Output is correct
49 Correct 2064 ms 676536 KB Output is correct
50 Correct 1903 ms 637336 KB Output is correct
51 Correct 2029 ms 637040 KB Output is correct
52 Correct 909 ms 675212 KB Output is correct
53 Correct 1416 ms 151628 KB Output is correct