Submission #1097985

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097985		vjudge1	Examination (JOI19_examination)	C++17	Compilation error	0 ms	0 KiB

This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.

examination

#include <bits/stdc++.h>
// #ifndef ONLINE_JUDGE
// #include "/Users/quocbaonguyentran/Documents/VOI25/template/debug.cpp"
// #else
// #define debug(...) ;
// #endif
// using namespace std;
#define endl "\n"
#define ll long long
struct Fenwick
{
    vector<int> bit;
    Fenwick() {};
    Fenwick(int n) : bit(n + 1, 0) {}

    void update(int id, int val)
    {
        for (; id < int(bit.size()); id += id & (-id))
        {
            bit[id] += val;
        }
    }
    int sum(int id)
    {
        int sum = 0;
        for (; id > 0; id -= id & (-id))
        {
            sum += bit[id];
        }
        return sum;
    }
    int query(int l, int r)
    {
        return sum(r) - sum(l - 1);
    }
} tree;
vector<int> d;
int res[200005];
int n, s[100005], t[100005], q;
int qe[100005];
int ans[100005];
vector<tuple<int, int, int, int, char>> p;
vector<tuple<int, int, char>> query;
bool cmp(tuple<int, int, int, char> &a, tuple<int, int, int, char> &b)
{
    int l1 = get<0>(a);
    int l2 = get<0>(b);
    char v1 = get<3>(a);
    char v2 = get<3>(b);
    return l1 > l2 || l1 == l2 && v1 < v2;
}
bool cmp2(tuple<int, int, int, int, char> &a, tuple<int, int, int, int, char> &b)
{
    int l1 = get<0>(a);
    int l2 = get<0>(b);
    char v1 = get<4>(a);
    char v2 = get<4>(b);
    return l1 > l2 || l1 == l2 && v1 < v2;
}
void Cal(int l, int r)
{
    if (l >= r)
        return;
    int mid = (l + r) / 2;
    vector<tuple<int, int, int, char>> c;
    for (int i = l; i <= mid; i++)
    {
        auto [l, r, w] = query[i];
        if (w == '+')
        {
            c.push_back(make_tuple(l, r, i, w));
        }
    }
    for (int i = mid + 1; i <= r; i++)
    {
        auto [l, r, w] = query[i];
        if (w == '?')
        {
            c.push_back(make_tuple(l, r, i, w));
        }
    }
    sort(c.begin(), c.end(), cmp);
    vector<int> t;
    for (auto [l, r, i, w] : c)
    {
        if (w == '+')
        {
            t.push_back(r);
            tree.update(r, 1);
        }
        else
        {
            int val = tree.query(r, int(d.size()));
            res[i] += val;
        }
    }
    for (int i : t)
    {
        tree.update(i, -1);
    }
    Cal(l, mid);
    Cal(mid + 1, r);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        cin >> s[i] >> t[i];
        p.push_back({s[i] + t[i], s[i], t[i], i, '+'});
    }
    for (int i = 1; i <= q; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        p.push_back({c, a, b, i, '?'});
    }
    sort(p.begin(), p.end(), cmp2);
    query.push_back({0, 0, '0'});
    d.push_back(1);
    d.push_back(1e9);
    for (auto [w, l, r, id, type] : p)
    {
        query.push_back({l, r, type});
        if (type == '?')
            qe[query.size() - 1] = id;
        d.push_back(r);
    }
    sort(d.begin(), d.end());
    d.erase(unique(d.begin(), d.end()), d.end());
    for (auto &[l, r, w] : query)
    {
        r = lower_bound(d.begin(), d.end(), r) - d.begin() + 1;
    }
    tree = Fenwick(int(d.size()));
    Cal(1, n + q);
    for (int i = 1; i <= n + q; i++)
    {
        auto [l, r, w] = query[i];
        if (w == '?')
        {
            // cout << res[i] << " " << qe[i] << endl;
            ans[qe[i]] = res[i];
        }
    }
    for (int i = 1; i <= q; i++)
    {
        cout << ans[i] << endl;
    }
}

Compilation message (stderr)

examination.cpp:12:5: error: 'vector' does not name a type
   12 |     vector<int> bit;
      |     ^~~~~~
examination.cpp: In constructor 'Fenwick::Fenwick(int)':
examination.cpp:14:22: error: class 'Fenwick' does not have any field named 'bit'
   14 |     Fenwick(int n) : bit(n + 1, 0) {}
      |                      ^~~
examination.cpp: In member function 'void Fenwick::update(int, int)':
examination.cpp:18:25: error: 'bit' was not declared in this scope
   18 |         for (; id < int(bit.size()); id += id & (-id))
      |                         ^~~
examination.cpp: In member function 'int Fenwick::sum(int)':
examination.cpp:28:20: error: 'bit' was not declared in this scope
   28 |             sum += bit[id];
      |                    ^~~
examination.cpp: At global scope:
examination.cpp:37:1: error: 'vector' does not name a type
   37 | vector<int> d;
      | ^~~~~~
examination.cpp:42:1: error: 'vector' does not name a type
   42 | vector<tuple<int, int, int, int, char>> p;
      | ^~~~~~
examination.cpp:43:1: error: 'vector' does not name a type
   43 | vector<tuple<int, int, char>> query;
      | ^~~~~~
examination.cpp:44:10: error: 'tuple' was not declared in this scope; did you mean 'std::tuple'?
   44 | bool cmp(tuple<int, int, int, char> &a, tuple<int, int, int, char> &b)
      |          ^~~~~
      |          std::tuple
In file included from /usr/include/c++/10/bits/move.h:57,
                 from /usr/include/c++/10/bits/stl_pair.h:59,
                 from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from examination.cpp:1:
/usr/include/c++/10/type_traits:2631:11: note: 'std::tuple' declared here
 2631 |     class tuple;
      |           ^~~~~
examination.cpp:44:16: error: expected primary-expression before 'int'
   44 | bool cmp(tuple<int, int, int, char> &a, tuple<int, int, int, char> &b)
      |                ^~~
examination.cpp:44:21: error: expected primary-expression before 'int'
   44 | bool cmp(tuple<int, int, int, char> &a, tuple<int, int, int, char> &b)
      |                     ^~~
examination.cpp:44:26: error: expected primary-expression before 'int'
   44 | bool cmp(tuple<int, int, int, char> &a, tuple<int, int, int, char> &b)
      |                          ^~~
examination.cpp:44:31: error: expected primary-expression before 'char'
   44 | bool cmp(tuple<int, int, int, char> &a, tuple<int, int, int, char> &b)
      |                               ^~~~
examination.cpp:44:41: error: 'tuple' was not declared in this scope; did you mean 'std::tuple'?
   44 | bool cmp(tuple<int, int, int, char> &a, tuple<int, int, int, char> &b)
      |                                         ^~~~~
      |                                         std::tuple
In file included from /usr/include/c++/10/bits/move.h:57,
                 from /usr/include/c++/10/bits/stl_pair.h:59,
                 from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from examination.cpp:1:
/usr/include/c++/10/type_traits:2631:11: note: 'std::tuple' declared here
 2631 |     class tuple;
      |           ^~~~~
examination.cpp:44:47: error: expected primary-expression before 'int'
   44 | bool cmp(tuple<int, int, int, char> &a, tuple<int, int, int, char> &b)
      |                                               ^~~
examination.cpp:44:52: error: expected primary-expression before 'int'
   44 | bool cmp(tuple<int, int, int, char> &a, tuple<int, int, int, char> &b)
      |                                                    ^~~
examination.cpp:44:57: error: expected primary-expression before 'int'
   44 | bool cmp(tuple<int, int, int, char> &a, tuple<int, int, int, char> &b)
      |                                                         ^~~
examination.cpp:44:62: error: expected primary-expression before 'char'
   44 | bool cmp(tuple<int, int, int, char> &a, tuple<int, int, int, char> &b)
      |                                                              ^~~~
examination.cpp:44:70: error: expression list treated as compound expression in initializer [-fpermissive]
   44 | bool cmp(tuple<int, int, int, char> &a, tuple<int, int, int, char> &b)
      |                                                                      ^
examination.cpp:52:11: error: 'tuple' was not declared in this scope; did you mean 'std::tuple'?
   52 | bool cmp2(tuple<int, int, int, int, char> &a, tuple<int, int, int, int, char> &b)
      |           ^~~~~
      |           std::tuple
In file included from /usr/include/c++/10/bits/move.h:57,
                 from /usr/include/c++/10/bits/stl_pair.h:59,
                 from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from examination.cpp:1:
/usr/include/c++/10/type_traits:2631:11: note: 'std::tuple' declared here
 2631 |     class tuple;
      |           ^~~~~
examination.cpp:52:17: error: expected primary-expression before 'int'
   52 | bool cmp2(tuple<int, int, int, int, char> &a, tuple<int, int, int, int, char> &b)
      |                 ^~~
examination.cpp:52:22: error: expected primary-expression before 'int'
   52 | bool cmp2(tuple<int, int, int, int, char> &a, tuple<int, int, int, int, char> &b)
      |                      ^~~
examination.cpp:52:27: error: expected primary-expression before 'int'
   52 | bool cmp2(tuple<int, int, int, int, char> &a, tuple<int, int, int, int, char> &b)
      |                           ^~~
examination.cpp:52:32: error: expected primary-expression before 'int'
   52 | bool cmp2(tuple<int, int, int, int, char> &a, tuple<int, int, int, int, char> &b)
      |                                ^~~
examination.cpp:52:37: error: expected primary-expression before 'char'
   52 | bool cmp2(tuple<int, int, int, int, char> &a, tuple<int, int, int, int, char> &b)
      |                                     ^~~~
examination.cpp:52:47: error: 'tuple' was not declared in this scope; did you mean 'std::tuple'?
   52 | bool cmp2(tuple<int, int, int, int, char> &a, tuple<int, int, int, int, char> &b)
      |                                               ^~~~~
      |                                               std::tuple
In file included from /usr/include/c++/10/bits/move.h:57,
                 from /usr/include/c++/10/bits/stl_pair.h:59,
                 from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from examination.cpp:1:
/usr/include/c++/10/type_traits:2631:11: note: 'std::tuple' declared here
 2631 |     class tuple;
      |           ^~~~~
examination.cpp:52:53: error: expected primary-expression before 'int'
   52 | bool cmp2(tuple<int, int, int, int, char> &a, tuple<int, int, int, int, char> &b)
      |                                                     ^~~
examination.cpp:52:58: error: expected primary-expression before 'int'
   52 | bool cmp2(tuple<int, int, int, int, char> &a, tuple<int, int, int, int, char> &b)
      |                                                          ^~~
examination.cpp:52:63: error: expected primary-expression before 'int'
   52 | bool cmp2(tuple<int, int, int, int, char> &a, tuple<int, int, int, int, char> &b)
      |                                                               ^~~
examination.cpp:52:68: error: expected primary-expression before 'int'
   52 | bool cmp2(tuple<int, int, int, int, char> &a, tuple<int, int, int, int, char> &b)
      |                                                                    ^~~
examination.cpp:52:73: error: expected primary-expression before 'char'
   52 | bool cmp2(tuple<int, int, int, int, char> &a, tuple<int, int, int, int, char> &b)
      |                                                                         ^~~~
examination.cpp:52:81: error: expression list treated as compound expression in initializer [-fpermissive]
   52 | bool cmp2(tuple<int, int, int, int, char> &a, tuple<int, int, int, int, char> &b)
      |                                                                                 ^
examination.cpp: In function 'void Cal(int, int)':
examination.cpp:65:5: error: 'vector' was not declared in this scope
   65 |     vector<tuple<int, int, int, char>> c;
      |     ^~~~~~
examination.cpp:65:5: note: suggested alternatives:
In file included from /usr/include/c++/10/vector:67,
                 from /usr/include/c++/10/functional:62,
                 from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from examination.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:389:11: note:   'std::vector'
  389 |     class vector : protected _Vector_base<_Tp, _Alloc>
      |           ^~~~~~
In file included from /usr/include/c++/10/functional:62,
                 from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from examination.cpp:1:
/usr/include/c++/10/vector:86:13: note:   'std::pmr::vector'
   86 |       using vector = std::vector<_Tp, polymorphic_allocator<_Tp>>;
      |             ^~~~~~
examination.cpp:65:12: error: 'tuple' was not declared in this scope; did you mean 'std::tuple'?
   65 |     vector<tuple<int, int, int, char>> c;
      |            ^~~~~
      |            std::tuple
In file included from /usr/include/c++/10/bits/move.h:57,
                 from /usr/include/c++/10/bits/stl_pair.h:59,
                 from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from examination.cpp:1:
/usr/include/c++/10/type_traits:2631:11: note: 'std::tuple' declared here
 2631 |     class tuple;
      |           ^~~~~
examination.cpp:65:18: error: expected primary-expression before 'int'
   65 |     vector<tuple<int, int, int, char>> c;
      |                  ^~~
examination.cpp:68:26: error: 'query' was not declared in this scope
   68 |         auto [l, r, w] = query[i];
      |                          ^~~~~
examination.cpp:71:13: error: 'c' was not declared in this scope
   71 |             c.push_back(make_tuple(l, r, i, w));
      |             ^
examination.cpp:71:25: error: 'make_tuple' was not declared in this scope; did you mean 'std::make_tuple'?
   71 |             c.push_back(make_tuple(l, r, i, w));
      |                         ^~~~~~~~~~
      |                         std::make_tuple
In file included from /usr/include/c++/10/functional:54,
                 from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from examination.cpp:1:
/usr/include/c++/10/tuple:1474:5: note: 'std::make_tuple' declared here
 1474 |     make_tuple(_Elements&&... __args)
      |     ^~~~~~~~~~
examination.cpp:76:26: error: 'query' was not declared in this scope
   76 |         auto [l, r, w] = query[i];
      |                          ^~~~~
examination.cpp:79:13: error: 'c' was not declared in this scope
   79 |             c.push_back(make_tuple(l, r, i, w));
      |             ^
examination.cpp:79:25: error: 'make_tuple' was not declared in this scope; did you mean 'std::make_tuple'?
   79 |             c.push_back(make_tuple(l, r, i, w));
      |                         ^~~~~~~~~~
      |                         std::make_tuple
In file included from /usr/include/c++/10/functional:54,
                 from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from examination.cpp:1:
/usr/include/c++/10/tuple:1474:5: note: 'std::make_tuple' declared here
 1474 |     make_tuple(_Elements&&... __args)
      |     ^~~~~~~~~~
examination.cpp:82:10: error: 'c' was not declared in this scope
   82 |     sort(c.begin(), c.end(), cmp);
      |          ^
examination.cpp:82:5: error: 'sort' was not declared in this scope; did you mean 'std::sort'?
   82 |     sort(c.begin(), c.end(), cmp);
      |     ^~~~
      |     std::sort
In file included from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from examination.cpp:1:
/usr/include/c++/10/pstl/glue_algorithm_defs.h:296:1: note: 'std::sort' declared here
  296 | sort(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last);
      | ^~~~
examination.cpp:83:12: error: expected primary-expression before 'int'
   83 |     vector<int> t;
      |            ^~~
examination.cpp:88:15: error: request for member 'push_back' in 't', which is of non-class type 'int [100005]'
   88 |             t.push_back(r);
      |               ^~~~~~~~~
examination.cpp:93:41: error: 'd' was not declared in this scope
   93 |             int val = tree.query(r, int(d.size()));
      |                                         ^
examination.cpp: In function 'int main()':
examination.cpp:106:5: error: 'ios_base' has not been declared
  106 |     ios_base::sync_with_stdio(false);
      |     ^~~~~~~~
examination.cpp:107:5: error: 'cin' was not declared in this scope; did you mean 'std::cin'?
  107 |     cin.tie(NULL);
      |     ^~~
      |     std::cin
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:75,
                 from examination.cpp:1:
/usr/include/c++/10/iostream:60:18: note: 'std::cin' declared here
   60 |   extern istream cin;  /// Linked to standard input
      |                  ^~~
examination.cpp:112:9: error: 'p' was not declared in this scope
  112 |         p.push_back({s[i] + t[i], s[i], t[i], i, '+'});
      |         ^
examination.cpp:118:9: error: 'p' was not declared in this scope
  118 |         p.push_back({c, a, b, i, '?'});
      |         ^
examination.cpp:120:10: error: 'p' was not declared in this scope
  120 |     sort(p.begin(), p.end(), cmp2);
      |          ^
examination.cpp:120:5: error: 'sort' was not declared in this scope; did you mean 'std::sort'?
  120 |     sort(p.begin(), p.end(), cmp2);
      |     ^~~~
      |     std::sort
In file included from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from examination.cpp:1:
/usr/include/c++/10/pstl/glue_algorithm_defs.h:296:1: note: 'std::sort' declared here
  296 | sort(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last);
      | ^~~~
examination.cpp:121:5: error: 'query' was not declared in this scope
  121 |     query.push_back({0, 0, '0'});
      |     ^~~~~
examination.cpp:122:5: error: 'd' was not declared in this scope
  122 |     d.push_back(1);
      |     ^
examination.cpp:132:13: error: 'unique' was not declared in this scope; did you mean 'std::unique'?
  132 |     d.erase(unique(d.begin(), d.end()), d.end());
      |             ^~~~~~
      |             std::unique
In file included from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from examination.cpp:1:
/usr/include/c++/10/pstl/glue_algorithm_defs.h:234:1: note: 'std::unique' declared here
  234 | unique(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last);
      | ^~~~~~
examination.cpp:135:13: error: 'lower_bound' was not declared in this scope; did you mean 'std::lower_bound'?
  135 |         r = lower_bound(d.begin(), d.end(), r) - d.begin() + 1;
      |             ^~~~~~~~~~~
      |             std::lower_bound
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from examination.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:2031:5: note: 'std::lower_bound' declared here
 2031 |     lower_bound(_ForwardIterator __first, _ForwardIterator __last,
      |     ^~~~~~~~~~~
examination.cpp:150:9: error: 'cout' was not declared in this scope; did you mean 'std::cout'?
  150 |         cout << ans[i] << endl;
      |         ^~~~
      |         std::cout
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:75,
                 from examination.cpp:1:
/usr/include/c++/10/iostream:61:18: note: 'std::cout' declared here
   61 |   extern ostream cout;  /// Linked to standard output
      |                  ^~~~