QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #168934 | #4037. Absolute Pairwise Distance | nhuang685 | Compile Error | / | / | C++20 | 7.3kb | 2023-09-09 05:55:12 | 2023-09-09 05:55:13 |
Judging History
answer
/**
* @file qoj4037-1.cpp
* @author n685
* @brief
* @date 2023-09-06
*
*
*/
#include <bits/stdc++.h>
#ifdef LOCAL
std::ifstream cin;
std::ofstream cout;
using std::cerr;
#else
using std::cin;
using std::cout;
#define cerr \
if (false) \
std::cerr
#endif
#ifdef LOCAL
#include "dd/debug.h"
#define dbg(...) lineInfo(__LINE__, #__VA_ARGS__), dbg1(__VA_ARGS__)
#define dbgR(...) lineInfo(__LINE__, #__VA_ARGS__), dbg2(__VA_ARGS__)
#define dbgP(p, ...) \
lineInfo(__LINE__, #__VA_ARGS__ " proj"), dbg3(p, __VA_ARGS__)
#define dbgRP(p, ...) \
lineInfo(__LINE__, #__VA_ARGS__ " proj"), dbg4(p, __VA_ARGS__)
void nline() { cerr << '\n'; }
#else
#define dbg(...) 42
#define dbgR(...) 4242
#define dbgP(...) 420
#define dbgRP(...) 420420
void nline() {}
#endif
template <class T> struct CC {
std::vector<T> val;
void push(T a) { val.push_back(a); }
void init() {
std::sort(val.begin(), val.end());
val.erase(std::unique(val.begin(), val.end()), val.end());
}
int operator[](T a) const {
return static_cast<int>(std::distance(
val.begin(), std::lower_bound(val.begin(), val.end(), a)));
}
int size() const { return static_cast<int>(val.size()); }
};
#ifndef LOCAL
constexpr int B = 300;
#else
constexpr int B = 2;
#endif
template <class T> struct BIT {
int sz;
std::vector<T> val;
BIT() : sz(0) {}
BIT(int _sz) : sz(_sz), val(sz + 1) {}
void add(int i, T a) {
i++;
for (; i <= sz; i += (i & -i)) {
val[i] += a;
}
}
T sum(int i) {
i++;
T ans = 0;
for (; i > 0; i -= (i & -i)) {
ans += val[i];
}
return ans;
}
T query(int a, int b) { return sum(b) - sum(a - 1); }
};
// upd: O(sqrt(N)), query: O(1)
template <class T> struct PURQ {
int sz, bSz;
std::vector<T> val, bl;
PURQ(int _sz)
: sz(_sz), bSz((_sz + B - 1) / B), val(_sz), bl((_sz + B - 1) / B) {}
void add(int i, T a) {
for (; i < sz && i % B != 0; ++i) {
val[i] += a;
}
if (i == sz) {
return;
}
i /= B;
for (; i < bSz; ++i) {
bl[i] += a;
}
}
T sum(int i) {
if (i < 0) {
return 0;
}
return val[i] + bl[i / B];
}
T query(int a, int b) {
if (a > b) {
return 0;
}
return sum(b) - sum(a - 1);
}
};
int n, q;
int m;
std::vector<__int128_t> a;
std::vector<int> aa;
struct Q1 {
int l = -1, r = -1;
int ind = 0;
};
struct Q {
int l1 = -1, r1 = -1, l2 = -1, r2 = -1;
Q1 rr, rl, lr, ll;
};
namespace MO {
std::vector<Q1> qq;
std::vector<__int128_t> ans;
void insert(Q1 &q) {
q.ind = (int)qq.size() + 1;
qq.push_back(q);
}
void init() {
BIT<__int128_t> v1(m), v2(m);
BIT<int> f1(m), f2(m);
int k = (int)qq.size();
std::sort(qq.begin(), qq.end(), [&](auto a, auto b) {
return (a.l / B == b.l / B) ? a.r < b.r : a.l < b.l;
});
ans.resize(k + 1);
for (int i = 0; i <= qq[0].l; ++i) {
v1.add(aa[i], a[i]);
f1.add(aa[i], 1);
}
for (int i = 0; i <= qq[0].r; ++i) {
ans[qq[0].ind] += (v1.query(aa[i], m - 1) - f1.query(aa[i], m - 1) * a[i]) +
(f1.query(0, aa[i] - 1) * a[i] - v1.query(0, aa[i] - 1));
v2.add(aa[i], a[i]);
f2.add(aa[i], 1);
}
for (int j = 1; j < k; ++j) {
// transition from i - 1 to i
ans[qq[j].ind] = ans[qq[j - 1].ind];
bool ll = qq[j].l < qq[j - 1].l;
bool rr = qq[j - 1].r < qq[j].r;
if (ll) {
for (int i = qq[j - 1].l; i > qq[j].l; --i) {
ans[qq[j].ind] -=
(v2.query(aa[i], m - 1) - f2.query(aa[i], m - 1) * a[i]) +
(f2.query(0, aa[i] - 1) * a[i] - v2.query(0, aa[i] - 1));
v1.add(aa[i], -a[i]);
f1.add(aa[i], -1);
}
if (rr) {
for (int i = qq[j - 1].r + 1; i <= qq[j].r; ++i) {
ans[qq[j].ind] +=
(v1.query(aa[i], m - 1) - f1.query(aa[i], m - 1) * a[i]) +
(f1.query(0, aa[i] - 1) * a[i] - v1.query(0, aa[i] - 1));
v2.add(aa[i], a[i]);
f2.add(aa[i], 1);
}
} else {
for (int i = qq[j - 1].r; i > qq[j].r; --i) {
ans[qq[j].ind] -=
(v1.query(aa[i], m - 1) - f1.query(aa[i], m - 1) * a[i]) +
(f1.query(0, aa[i] - 1) * a[i] - v1.query(0, aa[i] - 1));
v2.add(aa[i], -a[i]);
f2.add(aa[i], -1);
}
}
} else {
if (rr) {
for (int i = qq[j - 1].r + 1; i <= qq[j].r; ++i) {
ans[qq[j].ind] +=
(v1.query(aa[i], m - 1) - f1.query(aa[i], m - 1) * a[i]) +
(f1.query(0, aa[i] - 1) * a[i] - v1.query(0, aa[i] - 1));
v2.add(aa[i], a[i]);
f2.add(aa[i], 1);
}
} else {
for (int i = qq[j - 1].r; i > qq[j].r; --i) {
ans[qq[j].ind] -=
(v1.query(aa[i], m - 1) - f1.query(aa[i], m - 1) * a[i]) +
(f1.query(0, aa[i] - 1) * a[i] - v1.query(0, aa[i] - 1));
v2.add(aa[i], -a[i]);
f2.add(aa[i], -1);
}
}
if (ll) {
for (int i = qq[j - 1].l; i > qq[j].l; --i) {
ans[qq[j].ind] -=
(v2.query(aa[i], m - 1) - f2.query(aa[i], m - 1) * a[i]) +
(f2.query(0, aa[i] - 1) * a[i] - v2.query(0, aa[i] - 1));
v1.add(aa[i], -a[i]);
f1.add(aa[i], -1);
}
} else {
for (int i = qq[j - 1].l + 1; i <= qq[j].l; ++i) {
ans[qq[j].ind] +=
(v2.query(aa[i], m - 1) - f2.query(aa[i], m - 1) * a[i]) +
(f2.query(0, aa[i] - 1) * a[i] - v2.query(0, aa[i] - 1));
v1.add(aa[i], a[i]);
f1.add(aa[i], 1);
}
}
}
}
}
}; // namespace MO
int main() {
#ifdef LOCAL
cin.open("input.txt");
cout.rdbuf()->pubsetbuf(0, 0);
cout.open("output.txt");
#else
cin.tie(nullptr)->sync_with_stdio(false);
#endif
cin >> n >> q;
a.resize(n);
CC<__int128_t> cc;
for (int i = 0; i < n; ++i) {
cin >> a[i];
cc.push(a[i]);
}
cc.init();
m = cc.size();
aa.resize(n);
for (int i = 0; i < n; ++i) {
aa[i] = cc[a[i]];
}
std::vector<Q> qq(q);
std::vector<Q1> q2;
auto create = [&](int a, int b) {
return Q1{std::min(a, b), std::max(a, b)};
};
for (int i = 0; i < q; ++i) {
cin >> qq[i].l1 >> qq[i].r1 >> qq[i].l2 >> qq[i].r2;
qq[i].l1--;
qq[i].l2--;
qq[i].r1--;
qq[i].r2--;
qq[i].rr = create(qq[i].r1, qq[i].r2);
MO::insert(qq[i].rr);
if (qq[i].l2 > 0) {
qq[i].rl = create(qq[i].r1, qq[i].l2 - 1);
MO::insert(qq[i].rl);
}
if (qq[i].l1 > 0) {
qq[i].lr = create(qq[i].l1 - 1, qq[i].r1);
MO::insert(qq[i].lr);
}
if (qq[i].l1 > 0 && qq[i].l2 > 0) {
qq[i].ll = create(qq[i].l1 - 1, qq[i].l2 - 1);
MO::insert(qq[i].ll);
}
}
MO::init();
std::vector<__int128_t> ans(q);
for (int i = 0; i < q; ++i) {
ans[i] = MO::ans[qq[i].rr.ind] - MO::ans[qq[i].rl.ind] -
MO::ans[qq[i].lr.ind] + MO::ans[qq[i].ll.ind];
cout << (int64_t)ans[i] << '\n';
}
}
Details
answer.code: In function ‘int main()’:
answer.code:235:9: error: no match for ‘operator>>’ (operand types are ‘std::istream’ {aka ‘std::basic_istream<char>’} and ‘__gnu_cxx::__alloc_traits<std::allocator<__int128>, __int128>::value_type’ {aka ‘__int128’})
235 | cin >> a[i];
In file included from /usr/include/c++/11/sstream:38,
from /usr/include/c++/11/complex:45,
from /usr/include/c++/11/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
from answer.code:9:
/usr/include/c++/11/istream:120:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(std::basic_istream<_CharT, _Traits>::__istream_type& (*)(std::basic_istream<_CharT, _Traits>::__istream_type&)) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]’ (near match)
120 | operator>>(__istream_type& (*__pf)(__istream_type&))
| ^~~~~~~~
/usr/include/c++/11/istream:120:7: note: conversion of argument 1 would be ill-formed:
answer.code:235:15: error: invalid conversion from ‘__gnu_cxx::__alloc_traits<std::allocator<__int128>, __int128>::value_type’ {aka ‘__int128’} to ‘std::basic_istream<char>::__istream_type& (*)(std::basic_istream<char>::__istream_type&)’ {aka ‘std::basic_istream<char>& (*)(std::basic_istream<char>&)’} [-fpermissive]
235 | cin >> a[i];
| ^
| |
| __gnu_cxx::__alloc_traits<std::allocator<__int128>, __int128>::value_type {aka __int128}
In file included from /usr/include/c++/11/sstream:38,
from /usr/include/c++/11/complex:45,
from /usr/include/c++/11/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
from answer.code:9:
/usr/include/c++/11/istream:124:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(std::basic_istream<_CharT, _Traits>::__ios_type& (*)(std::basic_istream<_CharT, _Traits>::__ios_type&)) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>; std::basic_istream<_CharT, _Traits>::__ios_type = std::basic_ios<char>]’ (near match)
124 | operator>>(__ios_type& (*__pf)(__ios_type&))
| ^~~~~~~~
/usr/include/c++/11/istream:124:7: note: conversion of argument 1 would be ill-formed:
answer.code:235:15: error: invalid conversion from ‘__gnu_cxx::__alloc_traits<std::allocator<__int128>, __int128>::value_type’ {aka ‘__int128’} to ‘std::basic_istream<char>::__ios_type& (*)(std::basic_istream<char>::__ios_type&)’ {aka ‘std::basic_ios<char>& (*)(std::basic_ios<char>&)’} [-fpermissive]
235 | cin >> a[i];
| ^
| |
| __gnu_cxx::__alloc_traits<std::allocator<__int128>, __int128>::value_type {aka __int128}
In file included from /usr/include/c++/11/sstream:38,
from /usr/include/c++/11/complex:45,
from /usr/include/c++/11/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
from answer.code:9:
/usr/include/c++/11/istream:131:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(std::ios_base& (*)(std::ios_base&)) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]’ (near match)
131 | operator>>(ios_base& (*__pf)(ios_base&))
| ^~~~~~~~
/usr/include/c++/11/istream:131:7: note: conversion of argument 1 would be ill-formed:
answer.code:235:15: error: invalid conversion from ‘__gnu_cxx::__alloc_traits<std::allocator<__int128>, __int128>::value_type’ {aka ‘__int128’} to ‘std::ios_base& (*)(std::ios_base&)’ [-fpermissive]
235 | cin >> a[i];
| ^
| |
| __gnu_cxx::__alloc_traits<std::allocator<__int128>, __int128>::value_type {aka __int128}
In file included from /usr/include/c++/11/sstream:38,
from /usr/include/c++/11/complex:45,
from /usr/include/c++/11/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
from answer.code:9:
/usr/include/c++/11/istream:168:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(bool&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]’ (near match)
168 | operator>>(bool& __n)
| ^~~~~~~~
/usr/include/c++/11/istream:168:7: note: conversion of argument 1 would be ill-formed:
answer.code:235:15: error: canno...