Submission #715195

#TimeUsernameProblemLanguageResultExecution timeMemory
715195aykhnExamination (JOI19_examination)C++14
22 / 100
3043 ms24184 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 MergeTree
{
    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<int> &arr)
    {
        if (l == r) return;
        if (l + 1 == r)
        {
            if (l >= arr.size()) tree[x].pb(inf);
            else tree[x].pb(arr[l]);
            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<int> &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);
    }
};

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<int> arr;

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

    MergeTree st;

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

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

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

            int rem = n - ind;

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

            cout << rem << endl;
            continue;
        }

        int cnt = 0;

        for (int i = 0; i < n; i++)
        {
            if (v[i].fi >= a && v[i].se >= b && v[i].fi + v[i].se >= c)
            {
                cnt++;
            }
        }
        cout << cnt << endl;
    }
}

Compilation message (stderr)

examination.cpp: In member function 'void MergeTree::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 MergeTree::_build(int, int, int, std::vector<int>&)':
examination.cpp:77:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |             if (l >= arr.size()) tree[x].pb(inf);
      |                 ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...