Submission #713464

#	Time	Username	Problem	Language	Result	Execution time	Memory
713464		boris_mihov	Examination (JOI19_examination)	C++17	100 / 100	242 ms	17628 KiB

examination

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

typedef long long llong;
const int MAXN = 100000 + 10;

int n, q;
struct Person
{
    int x, y;
    inline friend bool operator < (const Person &a, const Person &b)
    {
        return a.x < b.x;
    }
};

struct BIT
{
    int tree[MAXN];
    inline void reset()
    {
        std::fill(tree + 1, tree + 1 + n, 0);
    }

    inline void update(int pos, int value)
    {
        for (int idx = pos ; idx <= n ; idx += idx & (-idx))
        {
            tree[idx] += value;
        }
    }

    inline int query(int pos)
    {
        int ans = 0;
        for (int idx = pos ; idx > 0 ; idx -= idx & (-idx))
        {
            ans += tree[idx];
        }

        return ans;
    }
};

Person p[MAXN];
int answer[MAXN];

int first(int num)
{
    int l = 0, r = n + 1, mid;
    while (l < r - 1)
    {
        mid = (l + r) / 2;
        if (p[mid].x < num) l = mid;
        else r = mid;
    }

    return r;
}

// to, idx
int cntOf[MAXN];
std::vector <std::pair <int,int>> compr;
std::vector <std::pair <int,int>> bQueries[MAXN];
std::vector <std::pair <int,int>> sumQueries[MAXN];
BIT tree;

inline int firstBiggerCompr(int num)
{
    int l = -1, r = n, mid;
    while (l < r - 1)
    {
        mid = (l + r) / 2;
        if (compr[mid].first < num) l = mid;
        else r = mid;
    }

    if (l == -1) return 0;
    return cntOf[l];
}

void answerSUM()
{
    compr.reserve(n);
    for (int i = 1 ; i <= n ; ++i)
    {
        compr.push_back({p[i].x + p[i].y, i});               
    }

    int cnt = 0;
    std::sort(compr.begin(), compr.end());
    for (int i = 0 ; i < n ; ++i)
    {
        if (i == 0 || compr[i].first != compr[i - 1].first)
        {
            cnt++;
        }

        p[compr[i].second].x = cnt - p[compr[i].second].y;
        cntOf[i] = cnt;
    }

    for (int i = n ; i >= 1 ; --i)
    {
        tree.update(p[i].x + p[i].y, 1);
        for (const auto &[to, idx] : sumQueries[i])
        {
            if (idx < 0) answer[-idx] -= tree.query(n) - tree.query(firstBiggerCompr(to));
            else answer[idx] += tree.query(n) - tree.query(firstBiggerCompr(to));
        }
    }
}

void answerB()
{
    tree.reset();
    compr.clear();
    compr.reserve(n);
    for (int i = 1 ; i <= n ; ++i)
    {
        compr.push_back({p[i].y, i});               
    }

    int cnt = 0;
    std::sort(compr.begin(), compr.end());
    for (int i = 0 ; i < n ; ++i)
    {
        if (i == 0 || compr[i].first != compr[i - 1].first)
        {
            cnt++;
        }

        p[compr[i].second].y = cnt;
        cntOf[i] = cnt;
    }

    for (int i = n ; i >= 1 ; --i)
    {
        tree.update(p[i].y, 1);
        for (const auto &[to, idx] : bQueries[i])
        {
            answer[idx] += tree.query(n) - tree.query(firstBiggerCompr(to));
        }
    }
}

void solve()
{
    int a, b, c;
    std::sort(p + 1, p + 1 + n);
    for (int i = 1 ; i <= q ; ++i)
    {
        std::cin >> a >> b >> c;
        int firstL = first(a);
        int secondL = first(c - b);

        if (firstL < secondL)
        {
            sumQueries[firstL].push_back({c, i});
            sumQueries[secondL].push_back({c, -i});
        }

        if (std::max(firstL, secondL) <= n)
        {
            bQueries[std::max(firstL, secondL)].push_back({b, i});
        }
    }

    answerSUM();
    answerB();
}

void input()
{
    std::cin >> n >> q;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> p[i].x >> p[i].y;
    }
}

void output()
{
    for (int i = 1 ; i <= q ; ++i)
    {
        std::cout << answer[i] << '\n';
    }
}

void fastIO()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIO();
    input();
    solve();
    output();

    return 0;
}

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