oj.uz

Submission #717925

# Submission time Handle Problem Language Result Execution time Memory
717925 2023-04-02T21:04:11 Z vjudge1 Examination (JOI19_examination) C++17
100 / 100
 1970 ms 354776 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));
                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

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())
      |                 ~~^~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 31 ms 7892 KB Output is correct
8 Correct 31 ms 8016 KB Output is correct
9 Correct 30 ms 7892 KB Output is correct
10 Correct 28 ms 7860 KB Output is correct
11 Correct 30 ms 7892 KB Output is correct
12 Correct 26 ms 8020 KB Output is correct
13 Correct 32 ms 7932 KB Output is correct
14 Correct 33 ms 7884 KB Output is correct
15 Correct 29 ms 7980 KB Output is correct
16 Correct 24 ms 7904 KB Output is correct
17 Correct 25 ms 7892 KB Output is correct
18 Correct 22 ms 7892 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1660 ms 352324 KB Output is correct
2 Correct 1618 ms 352212 KB Output is correct
3 Correct 1607 ms 352176 KB Output is correct
4 Correct 1453 ms 351636 KB Output is correct
5 Correct 1338 ms 351488 KB Output is correct
6 Correct 1129 ms 350796 KB Output is correct
7 Correct 1690 ms 352240 KB Output is correct
8 Correct 1502 ms 352192 KB Output is correct
9 Correct 1447 ms 352084 KB Output is correct
10 Correct 1072 ms 351364 KB Output is correct
11 Correct 1104 ms 351348 KB Output is correct
12 Correct 964 ms 350400 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1660 ms 352324 KB Output is correct
2 Correct 1618 ms 352212 KB Output is correct
3 Correct 1607 ms 352176 KB Output is correct
4 Correct 1453 ms 351636 KB Output is correct
5 Correct 1338 ms 351488 KB Output is correct
6 Correct 1129 ms 350796 KB Output is correct
7 Correct 1690 ms 352240 KB Output is correct
8 Correct 1502 ms 352192 KB Output is correct
9 Correct 1447 ms 352084 KB Output is correct
10 Correct 1072 ms 351364 KB Output is correct
11 Correct 1104 ms 351348 KB Output is correct
12 Correct 964 ms 350400 KB Output is correct
13 Correct 1687 ms 352704 KB Output is correct
14 Correct 1622 ms 352896 KB Output is correct
15 Correct 1603 ms 352484 KB Output is correct
16 Correct 1461 ms 351996 KB Output is correct
17 Correct 1343 ms 351852 KB Output is correct
18 Correct 1109 ms 350884 KB Output is correct
19 Correct 1681 ms 352772 KB Output is correct
20 Correct 1754 ms 352596 KB Output is correct
21 Correct 1849 ms 352692 KB Output is correct
22 Correct 1133 ms 351260 KB Output is correct
23 Correct 1291 ms 351564 KB Output is correct
24 Correct 964 ms 350372 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 31 ms 7892 KB Output is correct
8 Correct 31 ms 8016 KB Output is correct
9 Correct 30 ms 7892 KB Output is correct
10 Correct 28 ms 7860 KB Output is correct
11 Correct 30 ms 7892 KB Output is correct
12 Correct 26 ms 8020 KB Output is correct
13 Correct 32 ms 7932 KB Output is correct
14 Correct 33 ms 7884 KB Output is correct
15 Correct 29 ms 7980 KB Output is correct
16 Correct 24 ms 7904 KB Output is correct
17 Correct 25 ms 7892 KB Output is correct
18 Correct 22 ms 7892 KB Output is correct
19 Correct 1660 ms 352324 KB Output is correct
20 Correct 1618 ms 352212 KB Output is correct
21 Correct 1607 ms 352176 KB Output is correct
22 Correct 1453 ms 351636 KB Output is correct
23 Correct 1338 ms 351488 KB Output is correct
24 Correct 1129 ms 350796 KB Output is correct
25 Correct 1690 ms 352240 KB Output is correct
26 Correct 1502 ms 352192 KB Output is correct
27 Correct 1447 ms 352084 KB Output is correct
28 Correct 1072 ms 351364 KB Output is correct
29 Correct 1104 ms 351348 KB Output is correct
30 Correct 964 ms 350400 KB Output is correct
31 Correct 1687 ms 352704 KB Output is correct
32 Correct 1622 ms 352896 KB Output is correct
33 Correct 1603 ms 352484 KB Output is correct
34 Correct 1461 ms 351996 KB Output is correct
35 Correct 1343 ms 351852 KB Output is correct
36 Correct 1109 ms 350884 KB Output is correct
37 Correct 1681 ms 352772 KB Output is correct
38 Correct 1754 ms 352596 KB Output is correct
39 Correct 1849 ms 352692 KB Output is correct
40 Correct 1133 ms 351260 KB Output is correct
41 Correct 1291 ms 351564 KB Output is correct
42 Correct 964 ms 350372 KB Output is correct
43 Correct 1837 ms 354776 KB Output is correct
44 Correct 1736 ms 354720 KB Output is correct
45 Correct 1708 ms 354624 KB Output is correct
46 Correct 1522 ms 353120 KB Output is correct
47 Correct 1396 ms 353072 KB Output is correct
48 Correct 1185 ms 350588 KB Output is correct
49 Correct 1970 ms 354524 KB Output is correct
50 Correct 1831 ms 354572 KB Output is correct
51 Correct 1769 ms 354364 KB Output is correct
52 Correct 1194 ms 352828 KB Output is correct
53 Correct 1136 ms 352356 KB Output is correct