Submission #715240

#	Time	Username	Problem	Language	Result	Execution time	Memory
715240		aykhn	Examination (JOI19_examination)	C++14	100 / 100	1974 ms	354732 KiB

examination

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define OPT ios_base::sync_with_stdio(0); \
            cin.tie(0); \
            cout.tie(0)

#define pii pair<int,int>
#define pll pair<ll,ll>
#define endl "\n"
#define all(v) v.begin(), v.end()
#define mpr make_pair
#define pb push_back
#define ts to_string
#define fi first
#define se second
#define inf 0x3F3F3F3F
#define bpc __builtin_popcount
#define print(v) for(int i = 0; i < v.size(); i++) \
                    cout << v[i] << " "; \
                    cout<<endl;

struct MTree
{
    int size;
    vector<vector<int>> tree;

    void init(int n)
    {
        size = 1;

        while (size < n) size *= 2;

        tree.resize(2*size);
    }

    void merge(vector<int> &a, vector<int> &b, vector<int> &f)
    {
        int i = 0;
        int j = 0;

        while (i < a.size() && j < b.size())
        {
            if (a[i] <= b[j])
            {
                f.pb(a[i]);
                i++;
            }
            else
            {
                f.pb(b[j]);
                j++;
            }
        }

        while (i < a.size())
        {
            f.pb(a[i]);
            i++;
        }

        while (j < b.size())
        {
            f.pb(b[j]);
            j++;
        }
    }

    void _build(int l, int r, int x, vector<pii> &arr)
    {
        if (l + 1 == r)
        {
            if (l >= arr.size()) tree[x].pb(inf);
            else tree[x].pb(arr[l].se);
            return;
        }

        int mid = (l + r) >> 1;

        _build(l, mid, 2*x+1, arr);
        _build(mid, r, 2*x+2, arr);

        merge(tree[2*x+1], tree[2*x+2], tree[x]);
    }

    void build(vector<pii> &arr)
    {
        _build(0, size, 0, arr);
    }

    int get(int lx, int rx, int l, int r, int x, int val)
    {
        if (l >= rx || r <= lx) return 0;

        if (l >= lx && r <= rx)
        {
            return lower_bound(tree[x].begin(), tree[x].end(), val) - tree[x].begin();
        }

        int mid = (l + r) >> 1;

        return get(lx, rx, l, mid, 2*x+1, val) + get(lx, rx, mid, r, 2*x+2, val);
    }

    int get(int l, int r, int val)
    {
        return get(l, r, 0, size, 0, val);
    }
};

struct MergeTree
{
    int size;
    vector<vector<pii>> tree;
    vector<MTree> sub;

    void init(int &n)
    {
        size = 1;

        while (size < n) size *= 2;

        tree.resize(2*size);
        sub.resize(2*size);
    }

    void merge(vector<pii> &a, vector<pii> &b, vector<pii> &f)
    {
        int i = 0;
        int j = 0;

        while (i < a.size() && j < b.size())
        {
            if (a[i].fi <= b[j].fi)
            {
                f.pb(a[i]);
                i++;
            }
            else
            {
                f.pb(b[j]);
                j++;
            }
        }

        while (i < a.size())
        {
            f.pb(a[i]);
            i++;
        }

        while (j < b.size())
        {
            f.pb(b[j]);
            j++;
        }
    }

    void _build(int l, int r, int x, vector<pii> &arr)
    {
        if (l + 1 == r)
        {
            if (l >= arr.size())
            {
                tree[x].pb(mpr(inf, inf));
                sub[x].init(tree[x].size());
                sub[x].build(tree[x]);
            }
            else
            {
                tree[x].pb(arr[l]);
                sub[x].init(tree[x].size());
                sub[x].build(tree[x]);
            }
            return;
        }

        int mid = (l + r) >> 1;

        _build(l, mid, 2*x+1, arr);
        _build(mid, r, 2*x+2, arr);

        merge(tree[2*x+1], tree[2*x+2], tree[x]);
        sub[x].init(tree[x].size());
        sub[x].build(tree[x]);
    }

    void build(vector<pii> &arr)
    {
        _build(0, size, 0, arr);
    }

    int get(int lx, int rx, int l, int r, int x, pii val)
    {
        if (l >= rx || r <= lx) return 0;
        if (l >= lx && r <= rx)
        {
            int ind = lower_bound(tree[x].begin(), tree[x].end(), mpr(val.fi, 0)) - tree[x].begin();
            int temp = sub[x].get(ind, tree[x].size(), val.se) + ind;
            return temp;
        }

        int mid = (l + r) >> 1;

        return get(lx, rx, l, mid, 2*x+1, val) + get(lx, rx, mid, r, 2*x+2, val);
    }

    int get(int l, int r, pii val)
    {
        return get(l, r, 0, size, 0, val);
    }
};

int n;

int main()
{
    int q;
    cin >> n >> q;

    vector<pii> v(n);

    for (int i = 0; i < n; i++)
    {
        cin >> v[i].fi >> v[i].se;
    }

    sort(all(v));

    vector<pii> arr;

    for (int i = 0; i < n; i++)
    {
        arr.pb(mpr(v[i].se, v[i].fi + v[i].se));
    }

    MergeTree st;

    st.init(n);
    st.build(arr);

    while (q--)
    {
        int a, b, c;
        cin >> a >> b >> c;

        int ind = lower_bound(v.begin(), v.end(), mpr(a, b)) - v.begin();

        int rem = n - ind;
        rem -= st.get(ind, n, mpr(b, c));

        cout << rem << endl;
    }
}

Compilation message (stderr)

examination.cpp: In member function 'void MTree::merge(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
examination.cpp:45:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         while (i < a.size() && j < b.size())
      |                ~~^~~~~~~~~~
examination.cpp:45:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         while (i < a.size() && j < b.size())
      |                                ~~^~~~~~~~~~
examination.cpp:59:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         while (i < a.size())
      |                ~~^~~~~~~~~~
examination.cpp:65:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         while (j < b.size())
      |                ~~^~~~~~~~~~
examination.cpp: In member function 'void MTree::_build(int, int, int, std::vector<std::pair<int, int> >&)':
examination.cpp:76:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |             if (l >= arr.size()) tree[x].pb(inf);
      |                 ~~^~~~~~~~~~~~~
examination.cpp: In member function 'void MergeTree::merge(std::vector<std::pair<int, int> >&, std::vector<std::pair<int, int> >&, std::vector<std::pair<int, int> >&)':
examination.cpp:135:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |         while (i < a.size() && j < b.size())
      |                ~~^~~~~~~~~~
examination.cpp:135:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |         while (i < a.size() && j < b.size())
      |                                ~~^~~~~~~~~~
examination.cpp:149:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |         while (i < a.size())
      |                ~~^~~~~~~~~~
examination.cpp:155:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |         while (j < b.size())
      |                ~~^~~~~~~~~~
examination.cpp: In member function 'void MergeTree::_build(int, int, int, std::vector<std::pair<int, int> >&)':
examination.cpp:166:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |             if (l >= arr.size())
      |                 ~~^~~~~~~~~~~~~

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