Submission #551962

#	Time	Username	Problem	Language	Result	Execution time	Memory
551962		wenqi	Examination (JOI19_examination)	C++17	100 / 100	2207 ms	676552 KiB

examination

// 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 (stderr)

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 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57