Submission #717925

#TimeUsernameProblemLanguageResultExecution timeMemory
717925vjudge1Examination (JOI19_examination)C++17
100 / 100
1970 ms354776 KiB
#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 == r) return;
        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 == r) return;
        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();
            return sub[x].get(ind, tree[x].size(), val.se) + ind;
        }
 
        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:77: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]
   77 |             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:136: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]
  136 |         while (i < a.size() && j < b.size())
      |                ~~^~~~~~~~~~
examination.cpp:136: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]
  136 |         while (i < a.size() && j < b.size())
      |                                ~~^~~~~~~~~~
examination.cpp:150: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]
  150 |         while (i < a.size())
      |                ~~^~~~~~~~~~
examination.cpp:156: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]
  156 |         while (j < b.size())
      |                ~~^~~~~~~~~~
examination.cpp: In member function 'void MergeTree::_build(int, int, int, std::vector<std::pair<int, int> >&)':
examination.cpp:168: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]
  168 |             if (l >= arr.size())
      |                 ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...