oj.uz

Submission #715216

# Submission time Handle Problem Language Result Execution time Memory
715216 2023-03-26T08:32:48 Z aykhn Examination (JOI19_examination) C++14
0 / 100
 1665 ms 337492 KB 
#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));
            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]);
        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 + 1 == r)
        {
            if (tree[x][0].fi >= val.fi && tree[x][0].se >= val.se) return 1;
            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);
        }

        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;

        if (!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;
            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

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())  tree[x].pb(mpr(inf, inf));
      |                 ~~^~~~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 47 ms 7508 KB Output is correct
8 Correct 41 ms 7508 KB Output is correct
9 Correct 41 ms 7532 KB Output is correct
10 Correct 41 ms 7488 KB Output is correct
11 Correct 31 ms 7508 KB Output is correct
12 Incorrect 30 ms 7508 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1665 ms 337492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1665 ms 337492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 47 ms 7508 KB Output is correct
8 Correct 41 ms 7508 KB Output is correct
9 Correct 41 ms 7532 KB Output is correct
10 Correct 41 ms 7488 KB Output is correct
11 Correct 31 ms 7508 KB Output is correct
12 Incorrect 30 ms 7508 KB Output isn't correct
13 Halted 0 ms 0 KB -