Submission #1252714

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252714		duckindog	Examination (JOI19_examination)	C++20	100 / 100	368 ms	26260 KiB

examination

#include <bits/stdc++.h>

using namespace std;

const int N = 100'000 + 10;
int n, q;
struct Stu { 
    int a, b;
    friend istream& operator >> (istream& is, Stu& rhs) { 
        return is >> rhs.a >> rhs.b;
    }
} stu[N];
struct Query { 
    int a, b, c, idx;
    friend istream& operator >> (istream& is, Query& rhs) { 
        return is >> rhs.a >> rhs.b >> rhs.c;
    }
} query[N];

namespace BIT { 
    vector<int> pos[N], bit[N];

    inline void listUpd(int x, int y) { 
        for (; x < N; x += x & -x) pos[x].push_back(y);
    }
    void build() { 
        for (int i = 1; i < N; ++i) { 
            sort(pos[i].begin(), pos[i].end());
            pos[i].erase(unique(pos[i].begin(), pos[i].end()), pos[i].end());
            bit[i].resize(pos[i].size() + 5);
        }
    }

    void upd(int x, int y, int value) { 
        for (; x < N; x += x & -x) { 
            int j = upper_bound(pos[x].begin(), pos[x].end(), y) - pos[x].begin();
            for (; j <= (int)pos[x].size(); j += j & -j) bit[x][j] += value;
        }
    }
    int que(int x, int y) { 
        int ret = 0;
        for (; x; x -= x & -x) { 
            int j = upper_bound(pos[x].begin(), pos[x].end(), y) - pos[x].begin();
            for (; j; j -= j & -j) ret += bit[x][j];
        }
        return ret;
    }
}
vector<int> allA, allB;

int answer[N];

int32_t main() { 
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> q;
    for (int i = 1; i <= n; ++i) cin >> stu[i];
    for (int i = 1; i <= q; ++i) cin >> query[i], query[i].idx = i;

    { // discrete
        for (int i = 1; i <= n; ++i) { 
            const auto& [a, b] = stu[i];
            allA.push_back(a);
            allB.push_back(b);
        }
        
        sort(allA.begin(), allA.end());
        allA.erase(unique(allA.begin(), allA.end()), allA.end());
    
        sort(allB.begin(), allB.end());
        allB.erase(unique(allB.begin(), allB.end()), allB.end());

        for (int i = 1; i <= n; ++i) { 
            auto& [a, b] = stu[i];
            a = upper_bound(allA.begin(), allA.end(), a) - allA.begin();
            b = upper_bound(allB.begin(), allB.end(), b) - allB.begin();
        }

        allA.insert(allA.begin(), -1);
        allB.insert(allB.begin(), -1);
    }

    for (int i = 1; i <= n; ++i) BIT::listUpd(stu[i].a, stu[i].b);
    BIT::build();

    sort(stu + 1, stu + n + 1, [](const auto& a, const auto& b) { 
        return allA[a.a] + allB[a.b] > allA[b.a] + allB[b.b];
    });
    sort(query + 1, query + q + 1, [](const auto& a, const auto& b) { 
        return a.c > b.c;
    });

    for (int i = 1, it = 1; i <= q; ++i) { 
        auto [a, b, c, idx] = query[i];
        a = lower_bound (allA.begin(), allA.end(), a) - allA.begin();
        b = lower_bound (allB.begin(), allB.end(), b) - allB.begin();
        for (; it <= n && allA[stu[it].a] + allB[stu[it].b] >= c; ++it) { 
            BIT::upd(stu[it].a, stu[it].b, 1);
        }

        answer[idx] = BIT::que(n, n) - BIT::que(a - 1, n) - BIT::que(n, b - 1) + BIT::que(a - 1, b - 1);
    }

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

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