| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 74041 | 2018-08-29T16:34:00 Z | kingpig9 | Fortune Telling 2 (JOI14_fortune_telling2) | C++11 | Compilation error |
0 ms | 0 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define debug(...) fprintf(stderr, __VA_ARGS__)
//#define debug(...)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))
const int MAXN = 1 << 20;
struct segtree {
int tr[2 * MAXN];
segtree() {
for (int i = 0; i < 2 * MAXN; i++) {
tr[i] = -1e9;
}
}
void update (int x, int v) {
x += MAXN;
tr[x] = v;
while (x >>= 1) {
tr[x] = max(tr[2 * x], tr[2 * x + 1]);
}
}
int query (int a, int b, int cur = 1, int lt = 0, int rt = MAXN) {
if (rt <= a || b <= lt) {
return -1e9;
}
if (a <= lt && rt <= b) {
return tr[cur];
}
int mid = (lt + rt) / 2;
return max(query(a, b, 2 * cur, lt, mid), query(a, b, 2 * cur + 1, mid, rt));
}
};
int N, K;
vector<pii> card;
vector<int> T;
vector<int> vals;
segtree seg = segtree();
int main() {
scanf("%d %d", &N, &K);
card.resize(N);
T.resize(K);
for (int i = 0; i < N; i++) {
scanf("%d %d", &card[i].fi, &card[i].se);
vals.push_back(card[i].fi);
vals.push_back(card[i].se);
}
for (int i = 0; i < K; i++) {
scanf("%d", &T[i]);
vals.push_back(T[i]);
}
sort(all(vals));
vals.resize(unique(all(vals)) - vals.begin());
for (int i = 0; i < N; i++) {
card[i].fi = lower_bound(all(vals), card[i].fi) - vals.begin();
card[i].se = lower_bound(all(vals), card[i].se) - vals.begin();
T[i] = lower_bound(all(vals), T[i]) - vals.begin();
}
vector<pii> vt;
for (int i = 0; i < K; i++) {
seg.update(T[i], i);
vt.push_back({T[i], i});
}
sort(all(vt));
sort(card, card + N, [] (pii a, pii b) { return max(a.fi, a.se) > max(b.fi, b.se); });
oset<int> certain; //ones that are certainly going to flip the card
ll ans = 0;
for (int i = 0; i < N; i++) {
int mnside = min(card[i].fi, card[i].se), mxside = max(card[i].fi, card[i].se);
while (!vt.empty() && vt.back().fi >= mxside) {
certain.insert(vt.back().se);
vt.pop_back();
}
int x = seg.query(mnside, mxside); //KEY IDEA: "maybe" is going to turn the card to the min. so certainly the last "maybe" will.
bool flip = (certain.size() - certain.order_of_key(x)) % 2;
int ind;
if (x == -1e9) {
ind = (flip ? card[i].se : card[i].fi);
} else {
ind = (flip ? mnside : mxside);
}
ans += vals[ind];
}
printf("%lld\n", ans);
}
Compilation message
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:88:18: error: no match for 'operator+' (operand types are 'std::vector<std::pair<int, int> >' and 'int')
sort(card, card + N, [] (pii a, pii b) { return max(a.fi, a.se) > max(b.fi, b.se); });
~~~~~^~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:67:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from fortune_telling2.cpp:1:
/usr/include/c++/7/bits/stl_iterator.h:397:5: note: candidate: template<class _Iterator> std::reverse_iterator<_Iterator> std::operator+(typename std::reverse_iterator<_Iterator>::difference_type, const std::reverse_iterator<_Iterator>&)
operator+(typename reverse_iterator<_Iterator>::difference_type __n,
^~~~~~~~
/usr/include/c++/7/bits/stl_iterator.h:397:5: note: template argument deduction/substitution failed:
fortune_telling2.cpp:88:20: note: mismatched types 'const std::reverse_iterator<_Iterator>' and 'int'
sort(card, card + N, [] (pii a, pii b) { return max(a.fi, a.se) > max(b.fi, b.se); });
^
In file included from /usr/include/c++/7/bits/stl_algobase.h:67:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from fortune_telling2.cpp:1:
/usr/include/c++/7/bits/stl_iterator.h:1198:5: note: candidate: template<class _Iterator> std::move_iterator<_IteratorL> std::operator+(typename std::move_iterator<_IteratorL>::difference_type, const std::move_iterator<_IteratorL>&)
operator+(typename move_iterator<_Iterator>::difference_type __n,
^~~~~~~~
/usr/include/c++/7/bits/stl_iterator.h:1198:5: note: template argument deduction/substitution failed:
fortune_telling2.cpp:88:20: note: mismatched types 'const std::move_iterator<_IteratorL>' and 'int'
sort(card, card + N, [] (pii a, pii b) { return max(a.fi, a.se) > max(b.fi, b.se); });
^
In file included from /usr/include/c++/7/string:52:0,
from /usr/include/c++/7/bits/locale_classes.h:40,
from /usr/include/c++/7/bits/ios_base.h:41,
from /usr/include/c++/7/ios:42,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from fortune_telling2.cpp:1:
/usr/include/c++/7/bits/basic_string.h:5876:5: note: candidate: template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Alloc> std::operator+(const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&, const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&)
operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
^~~~~~~~
/usr/include/c++/7/bits/basic_string.h:5876:5: note: template argument deduction/substitution failed:
fortune_telling2.cpp:88:20: note: 'std::vector<std::pair<int, int> >' is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>'
sort(card, card + N, [] (pii a, pii b) { return max(a.fi, a.se) > max(b.fi, b.se); });
^
In file included from /usr/include/c++/7/string:53:0,
from /usr/include/c++/7/bits/locale_classes.h:40,
from /usr/include/c++/7/bits/ios_base.h:41,
from /usr/include/c++/7/ios:42,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from fortune_telling2.cpp:1:
/usr/include/c++/7/bits/basic_string.tcc:1157:5: note: candidate: template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Alloc> std::operator+(const _CharT*, const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&)
operator+(const _CharT* __lhs,
^~~~~~~~
/usr/include/c++/7/bits/basic_string.tcc:1157:5: note: template argument deduction/substitution failed:
fortune_telling2.cpp:88:20: note: mismatched types 'const _CharT*' and 'std::vector<std::pair<int, int> >'
sort(card, card + N, [] (pii a, pii b) { return max(a.fi, a.se) > max(b.fi, b.se); });
^
In file included from /usr/include/c++/7/string:53:0,
from /usr/include/c++/7/bits/locale_classes.h:40,
from /usr/include/c++/7/bits/ios_base.h:41,
from /usr/include/c++/7/ios:42,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from fortune_telling2.cpp:1:
/usr/include/c++/7/bits/basic_string.tcc:1173:5: note: candidate: template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Alloc> std::operator+(_CharT, const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&)
operator+(_CharT __lhs, const basic_string<_CharT, _Traits, _Alloc>& __rhs)
^~~~~~~~
/usr/include/c++/7/bits/basic_string.tcc:1173:5: note: template argument deduction/substitution failed:
fortune_telling2.cpp:88:20: note: mismatched types 'const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>' and 'int'
sort(card, card + N, [] (pii a, pii b) { return max(a.fi, a.se) > max(b.fi, b.se); });
^
In file included from /usr/include/c++/7/string:52:0,
from /usr/include/c++/7/bits/locale_classes.h:40,
from /usr/include/c++/7/bits/ios_base.h:41,
from /usr/include/c++/7/ios:42,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from fortune_telling2.cpp:1:
/usr/include/c++/7/bits/basic_string.h:5913:5: note: candidate: template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Alloc> std::operator+(const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&, const _CharT*)
operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
^~~~~~~~
/usr/include/c++/7/bits/basic_string.h:5913:5: note: template argument deduction/substitution failed:
fortune_telling2.cpp:88:20: note: 'std::vector<std::pair<int, int> >' is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>'
sort(card, card + N, [] (pii a, pii b) { return max(a.fi, a.se) > max(b.fi, b.se); });
^
In file included from /usr/include/c++/7/string:52:0,
from /usr/include/c++/7/bits/locale_classes.h:40,
from /usr/include/c++/7/bits/ios_base.h:41,
from /usr/include/c++/7/ios:42,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from fortune_telling2.cpp:1:
/usr/include/c++/7/bits/basic_string.h:5929:5: note: candidate: template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Alloc> std::operator+(const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&, _CharT)
operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs, _CharT __rhs)
^~~~~~~~
/usr/include/c++/7/bits/basic_string.h:5929:5: note: template argument deduction/substitution failed:
fortune_telling2.cpp:88:20: note: 'std::vector<std::pair<int, int> >' is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>'
sort(card, card + N, [] (pii a, pii b) { return max(a.fi, a.se) > max(b.fi, b.se); });
^
In file included from /usr/include/c++/7/string:52:0,
from /usr/include/c++/7/bits/locale_classes.h:40,
from /usr/include/c++/7/bits/ios_base.h:41,
from /usr/include/c++/7/ios:42,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from fortune_telling2.cpp:1:
/usr/include/c++/7/bits/basic_string.h:5941:5: note: candidate: template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Alloc> std::operator+(std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&&, const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&)
operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
^~~~~~~~
/usr/include/c++/7/bits/basic_string.h:5941:5: note: template argument deduction/substitution failed:
fortune_telling2.cpp:88:20: note: 'std::vector<std::pair<int, int> >' is not derived from 'std::__cxx11::basic_string<_CharT, _Traits, _Alloc>'
sort(card, card + N, [] (pii a, pii b) { return max(a.fi, a.se) > max(b.fi, b.se); });
^
In file included from /usr/include/c++/7/string:52:0,
from /usr/include/c++/7/bits/locale_classes.h:40,
from /usr/include/c++/7/bits/ios_base.h:41,
from /usr/include/c++/7/ios:42,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from fortune_telling2.cpp:1:
/usr/include/c++/7/bits/basic_string.h:5947:5: note: candidate: template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Alloc> std::operator+(const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&, std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&&)
operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
^~~~~~~~
/usr/include/c++/7/bits/basic_string.h:5947:5: note: template argument deduction/substitution failed:
fortune_telling2.cpp:88:20: note: 'std::vector<std::pair<int, int> >' is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>'
sort(card, card + N, [] (pii a, pii b) { return max(a.fi, a.se) > max(b.fi, b.se); });
^
In file included from /usr/include/c++/7/string:52:0,
from /usr/include/c++/7/bits/locale_classes.h:40,
from /usr/include/c++/7/bits/ios_base.h:41,
from /usr/include/c++/7/ios:42,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from fortune_telling2.cpp:1:
/usr/include/c++/7/bits/basic_string.h:5953:5: note: candidate: template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Alloc> std::operator+(std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&&, std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&&)
operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
^~~~~~~~
/usr/include/c++/7/bits/basic_string.h:5953:5: note: template argument deduction/substitution failed:
fortune_telling2.cpp:88:20: note: 'std::vector<std::pair<int, int> >' is not derived from 'std::__cxx11::basic_string<_CharT, _Traits, _Alloc>'
sort(card, card + N, [] (pii a, pii b) { return max(a.fi, a.se) > max(b.fi, b.se); });
^
In file included from /usr/include/c++/7/string:52:0,
from /usr/include/c++/7/bits/locale_classes.h:40,
from /usr/include/c++/7/bits/ios_base.h:41,
from /usr/include/c++/7/ios:42,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from fortune_telling2.cpp:1:
/usr/include/c++/7/bits/basic_string.h:5965:5: note: candidate: template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Alloc> std::operator+(const _CharT*, std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&&)
operator+(const _CharT* __lhs,
^~~~~~~~
/usr/include/c++/7/bits/basic_string.h:5965:5: note: template argument deduction/substitution failed:
fortune_telling2.cpp:88:20: note: mismatched types 'const _CharT*' and 'std::vector<std::pair<int, int> >'
sort(card, card + N, [] (pii a, pii b) { return max(a.fi, a.se) > max(b.fi, b.se); });
^
In file included from /usr/include/c++/7/string:52:0,
from /usr/include/c++/7/bits/locale_classes.h:40,
from /usr/include/c++/7/bits/ios_base.h:41,
from /usr/include/c++/7/ios:42,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from fortune_telling2.cpp:1:
/usr/include/c++/7/bits/basic_string.h:5971:5: note: candidate: template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Alloc> std::operator+(_CharT, std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&&)
operator+(_CharT __lhs,
^~~~~~~~
/usr/include/c++/7/bits/basic_string.h:5971:5: note: template argument deduction/substitution failed:
fortune_telling2.cpp:88:20: note: mismatched types 'std::__cxx11::basic_string<_CharT, _Traits, _Alloc>' and 'int'
sort(card, card + N, [] (pii a, pii b) { return max(a.fi, a.se) > max(b.fi, b.se); });
^
In file included from /usr/include/c++/7/string:52:0,
from /usr/include/c++/7/bits/locale_classes.h:40,
from /usr/include/c++/7/bits/ios_base.h:41,
from /usr/include/c++/7/ios:42,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from fortune_telling2.cpp:1:
/usr/include/c++/7/bits/basic_string.h:5977:5: note: candidate: template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Alloc> std::operator+(std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&&, const _CharT*)
operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
^~~~~~~~
/usr/include/c++/7/bits/basic_string.h:5977:5: note: template argument deduction/substitution failed:
fortune_telling2.cpp:88:20: note: 'std::vector<std::pair<int, int> >' is not derived from 'std::__cxx11::basic_string<_CharT, _Traits, _Alloc>'
sort(card, card + N, [] (pii a, pii b) { return max(a.fi, a.se) > max(b.fi, b.se); });
^
In file included from /usr/include/c++/7/string:52:0,
from /usr/include/c++/7/bits/locale_classes.h:40,
from /usr/include/c++/7/bits/ios_base.h:41,
from /usr/include/c++/7/ios:42,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from fortune_telling2.cpp:1:
/usr/include/c++/7/bits/basic_string.h:5983:5: note: candidate: template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Alloc> std::operator+(std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&&, _CharT)
operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
^~~~~~~~
/usr/include/c++/7/bits/basic_string.h:5983:5: note: template argument deduction/substitution failed:
fortune_telling2.cpp:88:20: note: 'std::vector<std::pair<int, int> >' is not derived from 'std::__cxx11::basic_string<_CharT, _Traits, _Alloc>'
sort(card, card + N, [] (pii a, pii b) { return max(a.fi, a.se) > max(b.fi, b.se); });
^
In file included from /usr/include/c++/7/ccomplex:39:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from fortune_telling2.cpp:1:
/usr/include/c++/7/complex:326:5: note: candidate: template<class _Tp> std::complex<_Tp> std::operator+(const std::complex<_Tp>&, const std::complex<_Tp>&)
operator+(const complex<_Tp>& __x, const complex<_Tp>& __y)
^~~~~~~~
/usr/include/c++/7/complex:326:5: note: template argument deduction/substitution failed:
fortune_telling2.cpp:88:20: note: 'std::vector<std::pair<int, int> >' is not derived from 'const std::complex<_Tp>'
sort(card, card + N, [] (pii a, pii b) { return max(a.fi, a.se) > max(b.fi, b.se); });
^
In file included from /usr/include/c++/7/ccomplex:39:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from fortune_telling2.cpp:1:
/usr/include/c++/7/complex:335:5: note: candidate: template<class _Tp> std::complex<_Tp> std::operator+(const std::complex<_Tp>&, const _Tp&)
operator+(const complex<_Tp>& __x, const _Tp& __y)
^~~~~~~~
/usr/include/c++/7/complex:335:5: note: template argument deduction/substitution failed:
fortune_telling2.cpp:88:20: note: 'std::vector<std::pair<int, int> >' is not derived from 'const std::complex<_Tp>'
sort(card, card + N, [] (pii a, pii b) { return max(a.fi, a.se) > max(b.fi, b.se); });
^
In file included from /usr/include/c++/7/ccomplex:39:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from fortune_telling2.cpp:1:
/usr/include/c++/7/c