QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #298366 | #7901. Basic Substring Structure | ucup-team1134# | TL | 873ms | 11552kb | C++23 | 29.2kb | 2024-01-06 03:02:09 | 2024-01-06 03:02:09 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod1=999999893,mod2=999999937,MAX=200005,INF=1<<30;
struct Rollinghash{
string S;
int n;
int base1;
int base2;
vector<ll> h1,h2,ru1,ru2;
void make(string &T,int ba1,int ba2){
S=T;
n=S.size();
h1.assign(n+1,0);
h2.assign(n+1,0);
ru1.assign(n+1,0);
ru2.assign(n+1,0);
base1=ba1;
base2=ba2;
ru1[0]=1;
ru2[0]=1;
for(int i=1;i<=n;i++){
h1[i]=h1[i-1]*base1+ll(S[i-1]-'A');
h1[i]%=mod1;
h2[i]=h2[i-1]*base2+ll(S[i-1]-'A');
h2[i]%=mod2;
ru1[i]=ru1[i-1]*base1%mod1;
ru2[i]=ru2[i-1]*base2%mod2;
}
}
pair<ll,ll> ha(int l,int r){
pair<ll,ll> res;
res.fi=(h1[r]-h1[l]*ru1[r-l]%mod1+mod1)%mod1;
res.se=(h2[r]-h2[l]*ru2[r-l]%mod2+mod2)%mod2;
return res;
}//開区間
};
// BIT セグ木 遅延セグ木 のみ
// from: https://gist.github.com/yosupo06/ddd51afb727600fd95d9d8ad6c3c80c9
// (based on AtCoder STL)
#include <algorithm>
#include <array>
#ifdef _MSC_VER
#include <intrin.h>
#endif
namespace atcoder {
namespace internal {
int ceil_pow2(int n) {
int x = 0;
while ((1U << x) < (unsigned int)(n)) x++;
return x;
}
int bsf(unsigned int n) {
#ifdef _MSC_VER
unsigned long index;
_BitScanForward(&index, n);
return index;
#else
return __builtin_ctz(n);
#endif
}
} // namespace internal
} // namespace atcoder
#include <cassert>
#include <numeric>
#include <type_traits>
namespace atcoder {
namespace internal {
#ifndef _MSC_VER
template <class T>
using is_signed_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value ||
std::is_same<T, __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int128 =
typename std::conditional<std::is_same<T, __uint128_t>::value ||
std::is_same<T, unsigned __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using make_unsigned_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value,
__uint128_t,
unsigned __int128>;
template <class T>
using is_integral = typename std::conditional<std::is_integral<T>::value ||
is_signed_int128<T>::value ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_signed_int = typename std::conditional<(is_integral<T>::value &&
std::is_signed<T>::value) ||
is_signed_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<(is_integral<T>::value &&
std::is_unsigned<T>::value) ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<
is_signed_int128<T>::value,
make_unsigned_int128<T>,
typename std::conditional<std::is_signed<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type>::type;
#else
template <class T> using is_integral = typename std::is_integral<T>;
template <class T>
using is_signed_int =
typename std::conditional<is_integral<T>::value && std::is_signed<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<is_integral<T>::value &&
std::is_unsigned<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<is_signed_int<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type;
#endif
template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;
template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;
template <class T> using to_unsigned_t = typename to_unsigned<T>::type;
} // namespace internal
} // namespace atcoder
#include <cassert>
#include <vector>
namespace atcoder {
template <class T> struct fenwick_tree {
using U = internal::to_unsigned_t<T>;
public:
fenwick_tree() : _n(0) {}
fenwick_tree(int n) : _n(n), data(n) {}
void add(int p, T x) {
assert(0 <= p && p < _n);
p++;
while (p <= _n) {
data[p - 1] += U(x);
p += p & -p;
}
}
T sum(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
return sum(r) - sum(l);
}
private:
int _n;
std::vector<U> data;
U sum(int r) {
U s = 0;
while (r > 0) {
s += data[r - 1];
r -= r & -r;
}
return s;
}
};
} // namespace atcoder
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
namespace atcoder {
template <class S,
S (*op)(S, S),
S (*e)(),
class F,
S (*mapping)(F, S),
F (*composition)(F, F),
F (*id)()>
struct lazy_segtree {
public:
lazy_segtree() : lazy_segtree(0) {}
lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {
log = internal::ceil_pow2(_n);
size = 1 << log;
d = std::vector<S>(2 * size, e());
lz = std::vector<F>(size, id());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
S get(int p) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
return d[p];
}
S prod(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
if (l == r) return e();
l += size;
r += size;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push(r >> i);
}
S sml = e(), smr = e();
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S all_prod() { return d[1]; }
void apply(int p, F f) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
d[p] = mapping(f, d[p]);
for (int i = 1; i <= log; i++) update(p >> i);
}
void apply(int l, int r, F f) {
assert(0 <= l && l <= r && r <= _n);
if (l == r) return;
l += size;
r += size;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push((r - 1) >> i);
}
{
int l2 = l, r2 = r;
while (l < r) {
if (l & 1) all_apply(l++, f);
if (r & 1) all_apply(--r, f);
l >>= 1;
r >>= 1;
}
l = l2;
r = r2;
}
for (int i = 1; i <= log; i++) {
if (((l >> i) << i) != l) update(l >> i);
if (((r >> i) << i) != r) update((r - 1) >> i);
}
}
template <bool (*g)(S)> int max_right(int l) {
return max_right(l, [](S x) { return g(x); });
}
template <class G> int max_right(int l, G g) {
assert(0 <= l && l <= _n);
assert(g(e()));
if (l == _n) return _n;
l += size;
for (int i = log; i >= 1; i--) push(l >> i);
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!g(op(sm, d[l]))) {
while (l < size) {
push(l);
l = (2 * l);
if (g(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}
template <bool (*g)(S)> int min_left(int r) {
return min_left(r, [](S x) { return g(x); });
}
template <class G> int min_left(int r, G g) {
assert(0 <= r && r <= _n);
assert(g(e()));
if (r == 0) return 0;
r += size;
for (int i = log; i >= 1; i--) push((r - 1) >> i);
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!g(op(d[r], sm))) {
while (r < size) {
push(r);
r = (2 * r + 1);
if (g(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
int _n, size, log;
std::vector<S> d;
std::vector<F> lz;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
void all_apply(int k, F f) {
d[k] = mapping(f, d[k]);
if (k < size) lz[k] = composition(f, lz[k]);
}
void push(int k) {
all_apply(2 * k, lz[k]);
all_apply(2 * k + 1, lz[k]);
lz[k] = id();
}
};
} // namespace atcoder
#include <algorithm>
#include <cassert>
#include <vector>
namespace atcoder {
template <class S, S (*op)(S, S), S (*e)()> struct segtree {
public:
segtree() : segtree(0) {}
segtree(int n) : segtree(std::vector<S>(n, e())) {}
segtree(const std::vector<S>& v) : _n(int(v.size())) {
log = internal::ceil_pow2(_n);
size = 1 << log;
d = std::vector<S>(2 * size, e());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
S get(int p) {
assert(0 <= p && p < _n);
return d[p + size];
}
S prod(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
S sml = e(), smr = e();
l += size;
r += size;
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S all_prod() { return d[1]; }
template <bool (*f)(S)> int max_right(int l) {
return max_right(l, [](S x) { return f(x); });
}
template <class F> int max_right(int l, F f) {
assert(0 <= l && l <= _n);
assert(f(e()));
if (l == _n) return _n;
l += size;
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!f(op(sm, d[l]))) {
while (l < size) {
l = (2 * l);
if (f(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}
template <bool (*f)(S)> int min_left(int r) {
return min_left(r, [](S x) { return f(x); });
}
template <class F> int min_left(int r, F f) {
assert(0 <= r && r <= _n);
assert(f(e()));
if (r == 0) return 0;
r += size;
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!f(op(d[r], sm))) {
while (r < size) {
r = (2 * r + 1);
if (f(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
int _n, size, log;
std::vector<S> d;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};
} // namespace atcoder
using TT=int;
TT ff(TT a,TT b){
return min(a,b);
}
TT titi(){
return INF;
}
// 文字列
// from: https://gist.github.com/yosupo06/ddd51afb727600fd95d9d8ad6c3c80c9
// (based on AtCoder STL)
namespace atcoder {
namespace internal {
std::vector<int> sa_naive(const std::vector<int>& s) {
int n = int(s.size());
std::vector<int> sa(n);
std::iota(sa.begin(), sa.end(), 0);
std::sort(sa.begin(), sa.end(), [&](int l, int r) {
if (l == r) return false;
while (l < n && r < n) {
if (s[l] != s[r]) return s[l] < s[r];
l++;
r++;
}
return l == n;
});
return sa;
}
std::vector<int> sa_doubling(const std::vector<int>& s) {
int n = int(s.size());
std::vector<int> sa(n), rnk = s, tmp(n);
std::iota(sa.begin(), sa.end(), 0);
for (int k = 1; k < n; k *= 2) {
auto cmp = [&](int x, int y) {
if (rnk[x] != rnk[y]) return rnk[x] < rnk[y];
int rx = x + k < n ? rnk[x + k] : -1;
int ry = y + k < n ? rnk[y + k] : -1;
return rx < ry;
};
std::sort(sa.begin(), sa.end(), cmp);
tmp[sa[0]] = 0;
for (int i = 1; i < n; i++) {
tmp[sa[i]] = tmp[sa[i - 1]] + (cmp(sa[i - 1], sa[i]) ? 1 : 0);
}
std::swap(tmp, rnk);
}
return sa;
}
template <int THRESHOLD_NAIVE = 10, int THRESHOLD_DOUBLING = 40>
std::vector<int> sa_is(const std::vector<int>& s, int upper) {
int n = int(s.size());
if (n == 0) return {};
if (n == 1) return {0};
if (n == 2) {
if (s[0] < s[1]) {
return {0, 1};
} else {
return {1, 0};
}
}
if (n < THRESHOLD_NAIVE) {
return sa_naive(s);
}
if (n < THRESHOLD_DOUBLING) {
return sa_doubling(s);
}
std::vector<int> sa(n);
std::vector<bool> ls(n);
for (int i = n - 2; i >= 0; i--) {
ls[i] = (s[i] == s[i + 1]) ? ls[i + 1] : (s[i] < s[i + 1]);
}
std::vector<int> sum_l(upper + 1), sum_s(upper + 1);
for (int i = 0; i < n; i++) {
if (!ls[i]) {
sum_s[s[i]]++;
} else {
sum_l[s[i] + 1]++;
}
}
for (int i = 0; i <= upper; i++) {
sum_s[i] += sum_l[i];
if (i < upper) sum_l[i + 1] += sum_s[i];
}
auto induce = [&](const std::vector<int>& lms) {
std::fill(sa.begin(), sa.end(), -1);
std::vector<int> buf(upper + 1);
std::copy(sum_s.begin(), sum_s.end(), buf.begin());
for (auto d : lms) {
if (d == n) continue;
sa[buf[s[d]]++] = d;
}
std::copy(sum_l.begin(), sum_l.end(), buf.begin());
sa[buf[s[n - 1]]++] = n - 1;
for (int i = 0; i < n; i++) {
int v = sa[i];
if (v >= 1 && !ls[v - 1]) {
sa[buf[s[v - 1]]++] = v - 1;
}
}
std::copy(sum_l.begin(), sum_l.end(), buf.begin());
for (int i = n - 1; i >= 0; i--) {
int v = sa[i];
if (v >= 1 && ls[v - 1]) {
sa[--buf[s[v - 1] + 1]] = v - 1;
}
}
};
std::vector<int> lms_map(n + 1, -1);
int m = 0;
for (int i = 1; i < n; i++) {
if (!ls[i - 1] && ls[i]) {
lms_map[i] = m++;
}
}
std::vector<int> lms;
lms.reserve(m);
for (int i = 1; i < n; i++) {
if (!ls[i - 1] && ls[i]) {
lms.push_back(i);
}
}
induce(lms);
if (m) {
std::vector<int> sorted_lms;
sorted_lms.reserve(m);
for (int v : sa) {
if (lms_map[v] != -1) sorted_lms.push_back(v);
}
std::vector<int> rec_s(m);
int rec_upper = 0;
rec_s[lms_map[sorted_lms[0]]] = 0;
for (int i = 1; i < m; i++) {
int l = sorted_lms[i - 1], r = sorted_lms[i];
int end_l = (lms_map[l] + 1 < m) ? lms[lms_map[l] + 1] : n;
int end_r = (lms_map[r] + 1 < m) ? lms[lms_map[r] + 1] : n;
bool same = true;
if (end_l - l != end_r - r) {
same = false;
} else {
while (l < end_l) {
if (s[l] != s[r]) {
break;
}
l++;
r++;
}
if (l == n || s[l] != s[r]) same = false;
}
if (!same) rec_upper++;
rec_s[lms_map[sorted_lms[i]]] = rec_upper;
}
auto rec_sa =
sa_is<THRESHOLD_NAIVE, THRESHOLD_DOUBLING>(rec_s, rec_upper);
for (int i = 0; i < m; i++) {
sorted_lms[i] = lms[rec_sa[i]];
}
induce(sorted_lms);
}
return sa;
}
} // namespace internal
std::vector<int> suffix_array(const std::vector<int>& s, int upper) {
assert(0 <= upper);
for (int d : s) {
assert(0 <= d && d <= upper);
}
auto sa = internal::sa_is(s, upper);
return sa;
}
template <class T> std::vector<int> suffix_array(const std::vector<T>& s) {
int n = int(s.size());
std::vector<int> idx(n);
iota(idx.begin(), idx.end(), 0);
sort(idx.begin(), idx.end(), [&](int l, int r) { return s[l] < s[r]; });
std::vector<int> s2(n);
int now = 0;
for (int i = 0; i < n; i++) {
if (i && s[idx[i - 1]] != s[idx[i]]) now++;
s2[idx[i]] = now;
}
return internal::sa_is(s2, now);
}
std::vector<int> suffix_array(const std::string& s) {
int n = int(s.size());
std::vector<int> s2(n);
for (int i = 0; i < n; i++) {
s2[i] = s[i];
}
return internal::sa_is(s2, 255);
}
template <class T>
std::vector<int> lcp_array(const std::vector<T>& s,
const std::vector<int>& sa) {
int n = int(s.size());
assert(n >= 1);
std::vector<int> rnk(n);
for (int i = 0; i < n; i++) {
rnk[sa[i]] = i;
}
std::vector<int> lcp(n - 1);
int h = 0;
for (int i = 0; i < n; i++) {
if (h > 0) h--;
if (rnk[i] == 0) continue;
int j = sa[rnk[i] - 1];
for (; j + h < n && i + h < n; h++) {
if (s[j + h] != s[i + h]) break;
}
lcp[rnk[i] - 1] = h;
}
return lcp;
}
std::vector<int> lcp_array(const std::string& s, const std::vector<int>& sa) {
int n = int(s.size());
std::vector<int> s2(n);
for (int i = 0; i < n; i++) {
s2[i] = s[i];
}
return lcp_array(s2, sa);
}
template <class T> std::vector<int> z_algorithm(const std::vector<T>& s) {
int n = int(s.size());
if (n == 0) return {};
std::vector<int> z(n);
z[0] = 0;
for (int i = 1, j = 0; i < n; i++) {
int& k = z[i];
k = (j + z[j] <= i) ? 0 : std::min(j + z[j] - i, z[i - j]);
while (i + k < n && s[k] == s[i + k]) k++;
if (j + z[j] < i + z[i]) j = i;
}
z[0] = n;
return z;
}
std::vector<int> z_algorithm(const std::string& s) {
int n = int(s.size());
std::vector<int> s2(n);
for (int i = 0; i < n; i++) {
s2[i] = s[i];
}
return z_algorithm(s2);
}
} // namespace atcoder
ll rui1[MAX],rui2[MAX];
struct T{
ll ha1;
//ll ha2;
int len;
};
T f(T a,T b){
T res;
res.ha1=(a.ha1*rui1[b.len]+b.ha1)%mod1;
//res.ha2=(a.ha2*rui2[b.len]+b.ha2)%mod2;
res.len=a.len+b.len;
return res;
}
T ti(){
return {0,0};
}
int main(){
std::ifstream in("text.txt");
std::cin.rdbuf(in.rdbuf());
cin.tie(0);
ios::sync_with_stdio(false);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll ha1=rng()%mod1,ha2=rng()%mod2;
rui1[0]=rui2[0]=1;
for(int i=1;i<MAX;i++){
rui1[i]=rui1[i-1]*ha1%mod1;
rui2[i]=rui2[i-1]*ha2%mod2;
}
int Q;cin>>Q;
while(Q--){
int N;cin>>N;
vector<int> A(N);
for(int i=0;i<N;i++){
cin>>A[i];A[i]--;
//A[i]=rng()%N;
}
auto sa=atcoder::suffix_array(A,N);
auto lcp=atcoder::lcp_array(A,sa);
atcoder::segtree<TT,ff,titi> seg(lcp);
auto fff=[&](ll x){
T res;
res.ha1=(ll)(x+1);//*rui1[po]%mod1;
//res.ha2=(ll)(x+1);//*rui2[po]%mod2;
res.len=1;
return res;
};
vector<int> pos(N);
for(int i=0;i<si(sa);i++){
pos[sa[i]]=i;
}
atcoder::segtree<T,f,ti> rol(N);
for(int i=0;i<N;i++) rol.set(i,fff(A[i]));
/*
for(int i=0;i<N;i++){
for(int j=i+1;j<=N;j++) cout<<i<<" "<<j<<" "<<rol.prod(i,j).ha1<<" "<<rol.prod(i,j).ha2<<endl;
}
*/
auto common=[&](int a,int b){
if(a==b) return N-a;
int left=0,right=N-max(a,b)+1;
while(right-left>1){
int mid=(left+right)/2;
auto x=rol.prod(a,a+mid);
auto y=rol.prod(b,b+mid);
if(x.ha1==y.ha1) left=mid;
else right=mid;
}
return left;
/*
a=pos[a];
b=pos[b];
if(a>b) swap(a,b);
return seg.prod(a,b);
*/
};
auto commonko=[&](int a,int b){
if(a==b) return N-a;
a=pos[a];
b=pos[b];
if(a>b) swap(a,b);
return seg.prod(a,b);
};
vector<ll> imoa(N+2),imob(N+2),ng(N+2);
vector<map<int,ll>> MA(N);
ll defans=0;
for(int i=0;i<N;i++){
ll x=commonko(i,0);
defans+=x;
//cout<<i<<" "<<x<<endl;
if(i){
if(0+x<=i){
imoa[0]++;
imoa[x]--;
imob[0]+=(-x);
imob[x]-=(-x);
imoa[i]++;
imoa[i+x]--;
imob[i]-=(i+x);
imob[i+x]+=(i+x);
}else{
imoa[0]++;
imoa[i]--;
imob[0]+=(-x);
imob[i]-=(-x);
imoa[i]++;
imoa[i+x]--;
imob[i]-=(i+x);
imob[i+x]+=(i+x);
}
}
if(i+x==N){
}else{
{
rol.set(x,fff(N+N));
ll y1=common(0,i);
rol.set(x,fff(A[i+x]));
ll y2=common(0,i);
MA[x][A[i+x]]+=y2-y1;
rol.set(x,fff(A[x]));
//cout<<i<<" "<<common(0,i)<<" "<<y1<<" "<<y2<<endl;
}
{
rol.set(i+x,fff(N+N));
ll y1=common(0,i);
rol.set(i+x,fff(A[x]));
ll y2=common(0,i);
MA[i+x][A[x]]+=y2-y1;
rol.set(i+x,fff(A[i+x]));
//cout<<i<<" "<<common(0,i)<<" "<<y1<<" "<<y2<<endl;
}
}
}
//for(int i=0;i<N;i++) imoa[i]*=-1;
for(int i=0;i<N;i++){
if(i) imoa[i]+=imoa[i-1];
if(i) imob[i]+=imob[i-1];
ng[i]=imoa[i]*i+imob[i];
//cout<<ng[i]<<" ";
}
ll ans=0;
for(int i=0;i<N;i++){
ll ma=-(1LL<<60);
if(si(MA[i])==N-1){
for(auto [a,b]:MA[i]) chmax(ma,b);
}else{
for(auto [a,b]:MA[i]) chmax(ma,b);
chmax(ma,0LL);
}
ma+=defans;
ma+=ng[i];
ans+=(ma^(i+1));
//cout<<ma<<" ";
}
//cout<<defans<<endl;
cout<<ans<<"\n";
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 6712kb
input:
2 4 2 1 1 2 12 1 1 4 5 1 4 1 9 1 9 8 10
output:
15 217
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 36ms
memory: 6728kb
input:
10000 8 2 1 2 1 1 1 2 2 9 2 2 1 2 1 2 1 2 1 15 2 1 2 1 1 1 1 2 2 1 2 1 2 2 1 2 1 1 10 2 1 1 1 2 2 1 1 2 2 3 2 1 2 11 1 2 2 1 1 2 1 2 2 1 1 14 2 1 1 1 1 2 1 1 1 2 2 1 2 1 12 2 2 2 1 2 2 2 1 1 2 1 2 4 2 1 1 2 8 1 2 2 2 1 2 1 1 8 1 1 2 1 2 1 1 1 6 2 1 1 1 2 2 14 2 2 1 1 1 1 2 2 2 1 2 2 1 1 10 1 2 2 1 1...
output:
94 128 347 3 211 9 265 363 278 15 95 114 58 348 225 3 335 364 377 316 3 19 122 66 15 83 36 258 11 63 28 90 85 103 252 191 21 48 303 63 102 20 24 68 316 362 266 309 355 281 326 281 231 312 3 330 54 328 3 69 32 147 322 39 338 90 242 3 165 346 245 20 155 3 404 393 392 81 269 360 20 54 21 279 3 17 351 3...
result:
ok 10000 lines
Test #3:
score: 0
Accepted
time: 87ms
memory: 6728kb
input:
10000 17 1 2 2 2 2 2 2 2 1 1 2 2 1 2 1 2 2 17 2 1 1 1 1 2 2 2 1 1 1 1 1 2 2 2 2 13 2 2 2 1 2 2 2 2 1 1 1 1 1 12 2 2 1 2 1 2 2 1 1 1 1 1 13 2 2 2 1 1 1 1 2 2 2 2 1 1 20 2 1 2 2 1 2 2 2 2 2 2 1 2 2 2 2 1 2 1 1 13 1 2 1 2 2 2 1 2 1 2 1 1 1 20 2 1 1 2 2 1 2 2 1 1 2 1 2 2 2 2 2 1 2 2 12 2 1 2 1 1 2 2 1 2...
output:
392 434 308 252 302 895 343 867 282 249 717 194 252 350 230 427 439 279 340 384 380 292 218 312 271 810 275 211 460 388 365 342 773 203 238 857 720 497 514 443 618 777 372 242 337 232 324 837 289 480 366 681 358 281 320 529 451 309 250 326 315 744 307 841 133 214 411 788 332 365 488 157 760 278 421 ...
result:
ok 10000 lines
Test #4:
score: 0
Accepted
time: 89ms
memory: 6740kb
input:
10000 10 3 3 1 2 2 3 3 3 2 3 13 1 2 1 2 1 1 3 1 2 2 1 3 1 14 1 2 1 2 3 3 2 3 1 2 2 2 3 3 10 1 1 1 1 1 1 3 2 1 2 19 1 3 3 3 1 3 3 2 1 1 1 3 2 2 1 2 1 3 2 12 1 3 1 3 1 1 3 2 3 3 2 3 11 1 1 1 2 2 3 1 1 3 1 1 12 3 2 2 1 3 3 2 1 1 3 3 2 11 2 2 3 2 3 1 3 1 2 1 1 20 3 1 2 2 3 1 3 3 1 3 3 2 3 3 3 2 3 1 1 2 ...
output:
191 285 325 207 420 281 215 280 151 754 365 199 94 418 318 377 414 285 373 362 111 358 332 117 185 326 89 404 229 386 307 285 421 232 321 329 506 372 386 364 153 582 313 356 152 129 424 366 382 280 363 370 273 294 388 389 807 388 459 280 114 310 211 368 150 166 793 211 793 393 102 427 399 408 584 38...
result:
ok 10000 lines
Test #5:
score: 0
Accepted
time: 84ms
memory: 6680kb
input:
10000 14 9 9 13 6 3 8 7 10 5 9 14 2 12 5 15 9 12 2 2 8 4 2 11 4 4 8 3 8 13 15 19 5 7 1 2 9 2 16 9 15 8 19 9 3 18 8 8 1 12 6 14 9 8 2 11 7 2 12 5 14 14 10 5 7 2 11 4 4 2 9 9 11 10 3 3 2 2 14 8 2 9 10 10 11 6 9 12 5 5 4 9 2 20 4 5 3 13 15 18 12 6 2 8 11 12 6 10 14 14 10 14 13 12 14 11 9 7 5 12 12 5 3 ...
output:
307 362 380 107 97 137 380 108 135 299 312 265 99 362 379 361 332 380 129 367 97 380 97 107 363 107 132 367 97 88 363 314 100 382 354 349 383 95 359 306 340 133 382 106 395 361 374 105 292 385 360 359 365 381 378 107 374 111 357 105 365 319 379 102 364 89 107 374 128 101 360 115 363 107 106 116 92 3...
result:
ok 10000 lines
Test #6:
score: 0
Accepted
time: 281ms
memory: 6796kb
input:
1331 128 1 1 2 1 1 1 1 1 1 1 1 1 1 2 2 2 1 1 2 1 2 2 1 1 2 1 2 1 2 1 2 2 1 2 1 2 2 2 1 2 1 2 2 2 2 2 1 2 1 2 2 1 1 2 2 1 1 1 1 2 2 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1 1 2 2 2 2 2 1 2 1 2 1 2 2 1 1 2 1 1 2 2 2 1 1 2 2 2 1 2 2 2 1 2 1 1 1 2 2 1 1 1 2 1 1 1 1 1 1 1 2 2 2 2 115 1 2 2 1 2 2 1 2 2 1 2 1 2 2 2 1...
output:
41073 22779 19964 77764 77960 62759 68522 21651 24781 42049 74437 19840 74378 68878 20605 34809 20231 20004 50820 29156 52217 53156 23540 67367 57400 46500 19870 60423 66032 51371 59540 51300 48277 22751 77712 65779 21946 37124 65635 40091 27911 55656 54005 18564 25013 64077 46260 21753 62329 69899 ...
result:
ok 1331 lines
Test #7:
score: 0
Accepted
time: 522ms
memory: 6960kb
input:
131 1471 2 3 2 3 1 2 2 1 1 1 1 2 1 3 2 1 1 1 2 2 2 2 2 2 3 1 3 2 1 2 3 2 3 1 3 1 2 1 3 1 3 1 3 2 2 1 3 3 3 1 1 1 3 2 2 2 1 2 1 3 1 3 3 1 2 2 1 2 3 1 3 1 3 3 2 1 3 3 2 3 2 2 2 1 3 2 1 2 2 1 3 1 1 3 2 3 1 1 2 1 2 3 2 1 3 3 2 2 2 2 1 1 1 2 3 1 1 3 3 2 3 2 1 3 1 3 3 2 2 1 2 1 1 2 1 3 2 1 2 2 3 2 2 1 1 3...
output:
4103972 1822893 4056671 4581950 1797128 5452459 5578024 6135700 4325429 1769997 1239977 1589696 5346072 1818448 5380837 3882106 3814365 1823901 4911982 5946018 5208392 4261893 1767953 5781183 4624024 1795249 1600563 1677098 4679442 4113663 1685240 1576241 5128042 1618422 4440641 4326472 5703872 3748...
result:
ok 131 lines
Test #8:
score: 0
Accepted
time: 528ms
memory: 7012kb
input:
131 1104 15 10 15 18 8 16 25 26 11 19 4 5 9 15 20 8 8 1 5 12 6 15 15 9 19 6 20 8 9 10 12 1 7 26 9 15 26 14 18 24 25 4 9 20 16 18 25 10 8 2 15 14 26 19 22 17 8 7 23 19 22 26 23 4 26 8 16 6 19 5 17 4 9 25 7 14 19 26 9 21 23 7 20 2 12 22 23 24 20 11 23 23 7 13 6 26 25 10 8 17 23 15 14 20 16 7 21 8 11 1...
output:
1585911 1671116 2074604 2071604 2066710 1571959 1699180 1597972 1573443 2062834 1968749 1670339 1696389 1700722 1574014 1673122 6093159 1965764 1966052 2084891 1597710 1989656 2054890 1659456 1601397 1982947 1675608 2075393 1694022 1992153 6012239 1675824 1987812 1589514 2063346 1986943 1571712 1671...
result:
ok 131 lines
Test #9:
score: 0
Accepted
time: 873ms
memory: 11552kb
input:
14 554 232 178 169 417 93 38 93 537 212 211 313 227 432 269 475 489 459 286 318 534 118 160 223 534 275 382 482 331 3 279 73 513 403 277 34 497 462 397 280 218 395 498 201 548 8 520 495 397 545 528 401 58 418 3 494 260 251 496 212 552 243 151 78 385 441 73 271 337 283 39 162 1 501 357 126 452 416 34...
output:
394027 127388087 408947528 132597056 403149770 403022905 410881136 404226176 134192573 106965642 108543004 108541542 109002658 408924618
result:
ok 14 lines
Test #10:
score: -100
Time Limit Exceeded
input:
1 200000 86045 57533 29508 181370 17680 186294 134595 82393 109229 189798 133533 194579 11412 112604 572 32659 76824 177596 106427 60375 98302 93821 34541 125615 108609 22507 166292 195457 151376 54630 166314 85832 192590 85410 149595 46737 54738 198246 56457 189628 135013 63949 28359 65601 162502 4...