제출 #720537

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
720537		thimote75	Examination (JOI19_examination)	C++14	100 / 100	533 ms	23568 KiB

examination

#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(_b) {}

    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;
}

컴파일 시 표준 에러 (stderr) 메시지

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