Submission #1097986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097986		vjudge1	Examination (JOI19_examination)	C++17	2 / 100	234 ms	18104 KiB

examination

#include <bits/stdc++.h>
// #ifndef ONLINE_JUDGE
// #include "/Users/quocbaonguyentran/Documents/VOI25/template/debug.cpp"
// #else
// #define debug(...) ;
// #endif
using namespace std;
#define endl "\n"
#define ll long long
struct Fenwick
{
    vector<int> bit;
    Fenwick() {};
    Fenwick(int n) : bit(n + 1, 0) {}

    void update(int id, int val)
    {
        for (; id < int(bit.size()); id += id & (-id))
        {
            bit[id] += val;
        }
    }
    int sum(int id)
    {
        int sum = 0;
        for (; id > 0; id -= id & (-id))
        {
            sum += bit[id];
        }
        return sum;
    }
    int query(int l, int r)
    {
        return sum(r) - sum(l - 1);
    }
} tree;
vector<int> d;
int res[200005];
int n, s[100005], t[100005], q;
int qe[100005];
int ans[100005];
vector<tuple<int, int, int, int, char>> p;
vector<tuple<int, int, char>> query;
bool cmp(tuple<int, int, int, char> &a, tuple<int, int, int, char> &b)
{
    int l1 = get<0>(a);
    int l2 = get<0>(b);
    char v1 = get<3>(a);
    char v2 = get<3>(b);
    return l1 > l2 || l1 == l2 && v1 < v2;
}
bool cmp2(tuple<int, int, int, int, char> &a, tuple<int, int, int, int, char> &b)
{
    int l1 = get<0>(a);
    int l2 = get<0>(b);
    char v1 = get<4>(a);
    char v2 = get<4>(b);
    return l1 > l2 || l1 == l2 && v1 < v2;
}
void Cal(int l, int r)
{
    if (l >= r)
        return;
    int mid = (l + r) / 2;
    vector<tuple<int, int, int, char>> c;
    for (int i = l; i <= mid; i++)
    {
        auto [l, r, w] = query[i];
        if (w == '+')
        {
            c.push_back(make_tuple(l, r, i, w));
        }
    }
    for (int i = mid + 1; i <= r; i++)
    {
        auto [l, r, w] = query[i];
        if (w == '?')
        {
            c.push_back(make_tuple(l, r, i, w));
        }
    }
    sort(c.begin(), c.end(), cmp);
    vector<int> t;
    for (auto [l, r, i, w] : c)
    {
        if (w == '+')
        {
            t.push_back(r);
            tree.update(r, 1);
        }
        else
        {
            int val = tree.query(r, int(d.size()));
            res[i] += val;
        }
    }
    for (int i : t)
    {
        tree.update(i, -1);
    }
    Cal(l, mid);
    Cal(mid + 1, r);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        cin >> s[i] >> t[i];
        p.push_back({s[i] + t[i], s[i], t[i], i, '+'});
    }
    for (int i = 1; i <= q; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        p.push_back({c, a, b, i, '?'});
    }
    sort(p.begin(), p.end(), cmp2);
    query.push_back({0, 0, '0'});
    d.push_back(1);
    d.push_back(1e9);
    for (auto [w, l, r, id, type] : p)
    {
        query.push_back({l, r, type});
        if (type == '?')
            qe[query.size() - 1] = id;
        d.push_back(r);
    }
    sort(d.begin(), d.end());
    d.erase(unique(d.begin(), d.end()), d.end());
    for (auto &[l, r, w] : query)
    {
        r = lower_bound(d.begin(), d.end(), r) - d.begin() + 1;
    }
    tree = Fenwick(int(d.size()));
    Cal(1, n + q);
    for (int i = 1; i <= n + q; i++)
    {
        auto [l, r, w] = query[i];
        if (w == '?')
        {
            // cout << res[i] << " " << qe[i] << endl;
            ans[qe[i]] = res[i];
        }
    }
    for (int i = 1; i <= q; i++)
    {
        cout << ans[i] << endl;
    }
}

Compilation message (stderr)

examination.cpp: In function 'bool cmp(std::tuple<int, int, int, char>&, std::tuple<int, int, int, char>&)':
examination.cpp:50:32: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   50 |     return l1 > l2 || l1 == l2 && v1 < v2;
      |                       ~~~~~~~~~^~~~~~~~~~
examination.cpp: In function 'bool cmp2(std::tuple<int, int, int, int, char>&, std::tuple<int, int, int, int, char>&)':
examination.cpp:58:32: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   58 |     return l1 > l2 || l1 == l2 && v1 < v2;
      |                       ~~~~~~~~~^~~~~~~~~~

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