제출 #152355

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
152355		fedoseevtimofey	Examination (JOI19_examination)	C++14	100 / 100	559 ms	26772 KiB

examination

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 1e5 + 7;
const int MX = 1e9 + 1;

int s[N], t[N];
vector <int> f[N];
vector <int> vals[N];

void addupd(int x, int y) {
    for (int i = x; i < N; i |= i + 1) vals[i].push_back(y);
}

void upd(int x, int y) {
    for (int i = x; i < N; i |= i + 1) {
        for (int j = lower_bound(vals[i].begin(), vals[i].end(), y) - vals[i].begin(); j < f[i].size(); j |= j + 1) {
            ++f[i][j];
        }
    }
}

int get(int x, int y) {
    int res = 0;
    for (int i = x; i >= 0; i &= i + 1, --i) {
        for (int j = upper_bound(vals[i].begin(), vals[i].end(), y) - vals[i].begin() - 1; j >= 0; j &= j + 1, --j) {
            res += f[i][j];
        }
    }
    return res;
}

struct Query {
    int a, b, c, id;
    bool operator <(const Query &other) const {
        return c > other.c;
    }
};

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.setf(ios::fixed); cout.precision(20);
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; ++i) cin >> s[i] >> t[i];
    vector <int> c;
    for (int i = 0; i < n; ++i) c.push_back(MX - s[i]);
    sort(c.begin(), c.end());
    c.resize(unique(c.begin(), c.end()) - c.begin());
    for (int i = 0; i < n; ++i) addupd(lower_bound(c.begin(), c.end(), MX - s[i]) - c.begin(), MX - t[i]);
    for (int i = 0; i < N; ++i) {
        sort(vals[i].begin(), vals[i].end());
        vals[i].resize(unique(vals[i].begin(), vals[i].end()) - vals[i].begin());
        f[i].resize(vals[i].size());
    }
    vector <int> p(n);
    iota(p.begin(), p.end(), 0);
    sort(p.begin(), p.end(), [&] (int i, int j) {
        return s[i] + t[i] > s[j] + t[j];
    });
    vector <Query> qr;
    for (int i = 0; i < q; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        qr.push_back({a, b, c, i});
    }
    sort(qr.begin(), qr.end());
    vector <int> ans(q);
    int uk = 0;
    for (auto qry : qr) {
        int a = qry.a, b = qry.b, sm = qry.c, id = qry.id;
        while (uk < n && s[p[uk]] + t[p[uk]] >= sm) {
            upd(lower_bound(c.begin(), c.end(), MX - s[p[uk]]) - c.begin(), MX - t[p[uk]]);
            ++uk;
        }
        ans[id] = get(upper_bound(c.begin(), c.end(), MX - a) - c.begin() - 1, MX - b);
    }
    for (int i = 0; i < q; ++i) cout << ans[i] << '\n';
}

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

examination.cpp: In function 'void upd(int, int)':
examination.cpp:21:90: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = lower_bound(vals[i].begin(), vals[i].end(), y) - vals[i].begin(); j < f[i].size(); j |= j + 1) {
                                                                                        ~~^~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57