oj.uz

Submission #720511

# Submission time Handle Problem Language Result Execution time Memory
720511 2023-04-08T11:30:47 Z thimote75 Examination (JOI19_examination) C++14
0 / 100
 281 ms 17072 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define num long long

#define point pair<num, num>
#define inf 1e18

typedef tree<
    pair<num, int>,
    null_type,
    less<pair<num, int>>,
    rb_tree_tag,
    tree_order_statistics_node_update> ordered_set;

struct Query {
    int id;
    int coef;

    num end_pos;
    num query;

    Query (int _id, int _c, num _p, num _q)
    : id(_id), coef(_c), end_pos(_p), query(_q) {}

    bool operator< (const Query &other) const {
        return end_pos < other.end_pos;
    }
};
struct SQQuery {
    int id;

    num a, b;

    SQQuery (int _id, num _a, num _b)
    : id(_id), a(_a), b(_a) {}

    bool operator< (const SQQuery &other) const {
        return a < other.a;
    }
};

void compute (vector<Query> &queries, vector<int> &result, vector<point> points) {
    sort(points.begin(), points.end());
    sort(queries.begin(), queries.end());

    ordered_set y_points;

    int mu = 0;
    for (Query &q : queries) {
        while (mu != points.size() && points[mu].first < q.end_pos) {
            y_points.insert({ points[mu].first + points[mu].second, mu });
            mu ++;
        }
    
        int res = y_points.size() - y_points.order_of_key({ q.query, -1 });
        result[q.id] += q.coef * res;
    }
}

void compute (vector<SQQuery> &queries, vector<int> &result, vector<point> points) {
    sort(queries.rbegin(), queries.rend());
    sort(points.rbegin(), points.rend());

    ordered_set y_points;

    int mu = 0;
    for (SQQuery &q : queries) {
        while (mu != points.size() && points[mu].first >= q.a) {
            y_points.insert({ points[mu].second, mu });
            mu ++;
        }

        int res = y_points.size() - y_points.order_of_key({ q.b, -1 });
        result[q.id] = res;
    }
}

int main () {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    int N, Q;
    cin >> N >> Q;

    vector<point> hp;
    vector<point> vp;
    for (int i = 0; i < N; i ++) {
        int x, y;
        cin >> x >> y;

        hp.push_back({ x, y });
        vp.push_back({ y, x });
    }

    vector<Query> hq;
    vector<Query> vq;
    vector<SQQuery> sq;

    for (int q = 0; q < Q; q ++) {
        int a, b, c;
        cin >> a >> b >> c;

        if (a + b > c) {
            sq.push_back(SQQuery(q, a, b));
        } else {
            hq.push_back(Query(q, 1, inf, c));
            hq.push_back(Query(q, -1, a, c));
            vq.push_back(Query(q, -1, b, c));
        }
    }

    vector<int> res(Q);

    compute(hq, res, hp);
    compute(vq, res, vp);
    compute(sq, res, hp);

    for (int i = 0; i < Q; i ++)
        cout << res[i] << endl;
}

Compilation message

examination.cpp: In function 'void compute(std::vector<Query>&, std::vector<int>&, std::vector<std::pair<long long int, long long int> >)':
examination.cpp:56:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         while (mu != points.size() && points[mu].first < q.end_pos) {
      |                ~~~^~~~~~~~~~~~~~~~
examination.cpp: In function 'void compute(std::vector<SQQuery>&, std::vector<int>&, std::vector<std::pair<long long int, long long int> >)':
examination.cpp:74:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         while (mu != points.size() && points[mu].first >= q.a) {
      |                ~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 57.0

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