Submission #441118

#	Time	Username	Problem	Language	Result	Execution time	Memory
441118		benedict0724	Examination (JOI19_examination)	C++17	100 / 100	372 ms	24884 KiB

examination

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int n, q;
pair<ll, int> X[100002], Y[100002], XY[100002];
ll x[100002], y[100002], xy[100002];
struct test1
{
    ll A, B, C; int i;
    test1() : test1(0, 0, 0, 0) {}
    test1(ll _A, ll _B, ll _C, int _i) : A(_A), B(_B), C(_C), i(_i) {}
    bool operator < (const test1 &O) const
    {
        return C < O.C;
    }
};
struct test2
{
    ll A, B; int i;
    test2() : test2(0, 0, 0) {}
    test2(ll _A, ll _B, int _i) :A(_A), B(_B), i(_i) {}
    bool operator < (const test2 &O) const
    {
        return A < O.A;
    }
};
ll S[100002], T[100002];
vector<test1> vec1;
vector<test2> vec2;

ll tree[400002][3];
ll ans[100002];
void add(int i, int l, int r, int idx, int type)
{
    if(l == r) { tree[i][type]++; return; }
    int m = (l + r)/2;
    if(idx <= m) add(i*2, l, m, idx, type);
    else add(i*2+1, m+1, r, idx, type);
    tree[i][type] = tree[i*2][type] + tree[i*2+1][type];
}
ll query(int i, int l, int r, int s, int e, int type)
{
    if(s > e) return 0;
    if(e < l || r < s) return 0;
    if(s <= l && r <= e) return tree[i][type];
    int m = (l + r)/2;
    return query(i*2, l, m, s, e, type) + query(i*2+1, m+1, r, s, e, type);
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(NULL);
    cin >> n >> q;
    for(int i=1;i<=n;i++)
    {
        cin >> S[i] >> T[i];
        X[i] = {S[i], i};
        Y[i] = {T[i], i};
        XY[i] = {S[i] + T[i], i};
    }
    sort(X+1, X+n+1);
    sort(Y+1, Y+n+1);
    sort(XY+1, XY+n+1);
    for(int i=1;i<=n;i++)
    {
        x[i] = X[i].first;
        y[i] = Y[i].first;
        xy[i] = XY[i].first;
    }

    for(int i=1;i<=q;i++)
    {
        ll A, B, C; cin >> A >> B >> C;
        if(A + B > C) vec2.push_back(test2(A, B, i));
        else vec1.push_back(test1(A, B, C, i));
    }
    sort(vec1.begin(), vec1.end());
    sort(vec2.begin(), vec2.end());

    int M1 = vec1.size(), M2 = vec2.size();
    int now = n;
    for(int i=M1-1;i>=0;i--)
    {
        while(now > 0 && XY[now].first >= vec1[i].C)
        {
            int id = lower_bound(x+1, x+n+1, S[XY[now].second]) - x;
            add(1, 1, n, id, 0);
            id = lower_bound(y+1, y+n+1, T[XY[now].second]) - y;
            add(1, 1, n, id, 1);
            now--;
        }
        int ia = lower_bound(x+1, x+n+1, vec1[i].A) - x;
        int ib = lower_bound(y+1, y+n+1, vec1[i].B) - y;
        ans[vec1[i].i] = query(1, 1, n, ia, n, 0) - query(1, 1, n, 1, ib-1, 1);
    }
    now = n;
    for(int i=M2-1;i>=0;i--)
    {
        while(now > 0 && X[now].first >= vec2[i].A)
        {
            int id = lower_bound(y+1, y+n+1, T[X[now].second]) - y;
            add(1, 1, n, id, 2);
            now--;
        }
        int ia = lower_bound(y+1, y+n+1, vec2[i].B) - y;
        ans[vec2[i].i] = query(1, 1, n, ia, n, 2);
    }

    for(int i=1;i<=q;i++)
    {
        cout << ans[i] << "\n";
    }
}

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