Submission #115333

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
115333	2019-06-06T17:24:48 Z	model_code	Hotel (CEOI11_hot)	C++17	Compilation error	0 ms	0 KB

hot

/* Alternative solution for task HOT
 * Author: Mateusz Baranowski
 * Time complexity: O((n+m) log(nm))
 */

#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;

#define INFTY 1000000001

int n, m, o, x, y;
vector< pair<int, int> > room, offer;
vector<int> next;
priority_queue<int> q;

int get_next(int x) {
  if (x != next[x]) next[x] = get_next(next[x]);
  return next[x];
}

int main() {
  scanf ("%d %d %d", &n, &m, &o);
  for (int i = 0; i < n; ++i) {
    scanf ("%d %d", &x, &y);
    room.push_back(make_pair(y, x));
    next.push_back(i);
  }
  next.push_back(n);
  room.push_back(make_pair(INFTY, INFTY));
  sort(room.begin(), room.end());
  for (int i = 0; i < m; ++i) {
    scanf ("%d %d", &x, &y);
    offer.push_back(make_pair(x, y));
  }
  sort(offer.begin(), offer.end());
  for (int i = m-1; i >= 0; --i) {
    y = offer[i].second;
    int a = 0, b = n;
    while (a < b) {
      int c = (a + b)/2;
      if (room[c].first < y) a = c + 1; else b = c;
    }
    y = get_next(a);
    if (y < n) {
      next[y] = y+1;
      q.push(offer[i].first - room[y].second);
    }
  }
  long long result = 0;
  while (o-- > 0 && !q.empty() && (x = q.top()) > 0) {
    result += x;
    q.pop();
  }
  printf ("%lld\n", result);
  return 0;
}

Compilation message

hot.cpp: In function 'int get_next(int)':
hot.cpp:20:12: error: reference to 'next' is ambiguous
   if (x != next[x]) next[x] = get_next(next[x]);
            ^~~~
hot.cpp:16:13: note: candidates are: std::vector<int> next
 vector<int> next;
             ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/deque:60,
                 from /usr/include/c++/7/queue:60,
                 from hot.cpp:7:
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:208:5: note:                 template<class _ForwardIterator> constexpr _ForwardIterator std::next(_ForwardIterator, typename std::iterator_traits<_Iter>::difference_type)
     next(_ForwardIterator __x, typename
     ^~~~
hot.cpp:20:21: error: reference to 'next' is ambiguous
   if (x != next[x]) next[x] = get_next(next[x]);
                     ^~~~
hot.cpp:16:13: note: candidates are: std::vector<int> next
 vector<int> next;
             ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/deque:60,
                 from /usr/include/c++/7/queue:60,
                 from hot.cpp:7:
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:208:5: note:                 template<class _ForwardIterator> constexpr _ForwardIterator std::next(_ForwardIterator, typename std::iterator_traits<_Iter>::difference_type)
     next(_ForwardIterator __x, typename
     ^~~~
hot.cpp:20:40: error: reference to 'next' is ambiguous
   if (x != next[x]) next[x] = get_next(next[x]);
                                        ^~~~
hot.cpp:16:13: note: candidates are: std::vector<int> next
 vector<int> next;
             ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/deque:60,
                 from /usr/include/c++/7/queue:60,
                 from hot.cpp:7:
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:208:5: note:                 template<class _ForwardIterator> constexpr _ForwardIterator std::next(_ForwardIterator, typename std::iterator_traits<_Iter>::difference_type)
     next(_ForwardIterator __x, typename
     ^~~~
hot.cpp:21:10: error: reference to 'next' is ambiguous
   return next[x];
          ^~~~
hot.cpp:16:13: note: candidates are: std::vector<int> next
 vector<int> next;
             ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/deque:60,
                 from /usr/include/c++/7/queue:60,
                 from hot.cpp:7:
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:208:5: note:                 template<class _ForwardIterator> constexpr _ForwardIterator std::next(_ForwardIterator, typename std::iterator_traits<_Iter>::difference_type)
     next(_ForwardIterator __x, typename
     ^~~~
hot.cpp: In function 'int main()':
hot.cpp:29:5: error: reference to 'next' is ambiguous
     next.push_back(i);
     ^~~~
hot.cpp:16:13: note: candidates are: std::vector<int> next
 vector<int> next;
             ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/deque:60,
                 from /usr/include/c++/7/queue:60,
                 from hot.cpp:7:
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:208:5: note:                 template<class _ForwardIterator> constexpr _ForwardIterator std::next(_ForwardIterator, typename std::iterator_traits<_Iter>::difference_type)
     next(_ForwardIterator __x, typename
     ^~~~
hot.cpp:31:3: error: reference to 'next' is ambiguous
   next.push_back(n);
   ^~~~
hot.cpp:16:13: note: candidates are: std::vector<int> next
 vector<int> next;
             ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/deque:60,
                 from /usr/include/c++/7/queue:60,
                 from hot.cpp:7:
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:208:5: note:                 template<class _ForwardIterator> constexpr _ForwardIterator std::next(_ForwardIterator, typename std::iterator_traits<_Iter>::difference_type)
     next(_ForwardIterator __x, typename
     ^~~~
hot.cpp:48:7: error: reference to 'next' is ambiguous
       next[y] = y+1;
       ^~~~
hot.cpp:16:13: note: candidates are: std::vector<int> next
 vector<int> next;
             ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/deque:60,
                 from /usr/include/c++/7/queue:60,
                 from hot.cpp:7:
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:208:5: note:                 template<class _ForwardIterator> constexpr _ForwardIterator std::next(_ForwardIterator, typename std::iterator_traits<_Iter>::difference_type)
     next(_ForwardIterator __x, typename
     ^~~~
hot.cpp:25:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d %d %d", &n, &m, &o);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
hot.cpp:27:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d %d", &x, &y);
     ~~~~~~^~~~~~~~~~~~~~~~~
hot.cpp:35:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d %d", &x, &y);
     ~~~~~~^~~~~~~~~~~~~~~~~