oj.uz

Submission #551958

# Submission time Handle Problem Language Result Execution time Memory
551958 2022-04-22T03:12:39 Z wenqi Examination (JOI19_examination) C++17
0 / 100
 1722 ms 150708 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<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) {}
    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:87: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]
   87 |         while (ptr < students.size() and students[ptr].first >= x)
      |                ~~~~^~~~~~~~~~~~~~~~~
examination.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |     scanf("%d%d", &N, &Q);
      |     ~~~~~^~~~~~~~~~~~~~~~
examination.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         scanf("%d%d", &s, &t);
      |         ~~~~~^~~~~~~~~~~~~~~~
examination.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         scanf("%d%d%d", &x, &y, &z);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
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 35 ms 27044 KB Output is correct
8 Correct 36 ms 27016 KB Output is correct
9 Correct 35 ms 27084 KB Output is correct
10 Correct 22 ms 4708 KB Output is correct
11 Correct 31 ms 27072 KB Output is correct
12 Incorrect 3 ms 456 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
0 / 21.0

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

Subtask #4
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 35 ms 27044 KB Output is correct
8 Correct 36 ms 27016 KB Output is correct
9 Correct 35 ms 27084 KB Output is correct
10 Correct 22 ms 4708 KB Output is correct
11 Correct 31 ms 27072 KB Output is correct
12 Incorrect 3 ms 456 KB Output isn't correct
13 Halted 0 ms 0 KB -