QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #925776 | #10099. Traveling in Cells 2 | maroonrk | WA | 1287ms | 229208kb | C++23 | 37.4kb | 2025-03-05 02:40:35 | 2025-03-05 02:40:35 |
Judging History
answer
#ifndef LOCAL
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#endif
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
//#define int ll
bool dbg=false;
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define eb emplace_back
#define a first
#define b second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
#ifdef LOCAL
#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
#else
#define dmp(x) void(0)
#endif
template<class t,class u> bool chmax(t&a,u b){if(a<b){a=b;return true;}else return false;}
template<class t,class u> bool chmin(t&a,u b){if(b<a){a=b;return true;}else return false;}
template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
using pi=pair<int,int>;
using vi=vc<int>;
using vvi=vc<vc<int>>;
template<class t,class u>
ostream& operator<<(ostream& os,const pair<t,u>& p){
return os<<"{"<<p.a<<","<<p.b<<"}";
}
template<class t> ostream& operator<<(ostream& os,const vc<t>& v){
os<<"{";
for(auto e:v)os<<e<<",";
return os<<"}";
}
#define mp make_pair
#define mt make_tuple
#define one(x) memset(x,-1,sizeof(x))
#define zero(x) memset(x,0,sizeof(x))
#ifdef LOCAL
void dmpr(ostream&os){os<<endl;}
template<class T,class... Args>
void dmpr(ostream&os,const T&t,const Args&... args){
os<<t<<" ";
dmpr(os,args...);
}
#define dmp2(...) dmpr(cerr,__LINE__,##__VA_ARGS__)
#else
#define dmp2(...) void(0)
#endif
using uint=unsigned;
using ull=unsigned long long;
template<class t,size_t n>
ostream& operator<<(ostream&os,const array<t,n>&a){
return os<<vc<t>(all(a));
}
ll rand_int(ll l, ll r) { //[l, r]
//#ifdef LOCAL
static mt19937_64 gen;
/*#else
static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
#endif*/
return uniform_int_distribution<ll>(l, r)(gen);
}
ll rand_int(ll k){ //[0,k)
return rand_int(0,k-1);
}
string rand_string(int n,char lw,char up){
string s(n,'?');
rep(i,n)s[i]=rand_int(lw,up);
return s;
}
int current_run_id,run_batch_size=1000;
int calc_random_limit(){
return current_run_id/run_batch_size+1;
}
template<class t>
void generate_single(t&a){
a=rand_int(1,calc_random_limit());
}
void generate_single(string&a){
int n;generate_single(n);
a=rand_string(n,'a','b');
}
template<class t,class u>
void generate_single(pair<t,u>&a){
generate_single(a.a);
generate_single(a.b);
}
//https://trap.jp/post/1224/
template<class... Args>
void input(Args&... a){
if(dbg){
(generate_single(a),...);
}else{
#ifdef USE_FAST_IO
sc.read(a...);
#else
(cin >> ... >> a);
#endif
}
}
#define INT(...) int __VA_ARGS__;input(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;input(__VA_ARGS__)
#define ULL(...) ull __VA_ARGS__;input(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;input(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;input(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__;input(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__;input(__VA_ARGS__)
#define overload3(a,b,c,d,...) d
#define VI2(name,size) vi name(size);rep(i_##name,size)input(name[i_##name]);
#define VI3(name,size,offset) vi name(size);rep(i_##name,size)input(name[i_##name]),name[i_##name]+=offset;
#define VI(...) overload3(__VA_ARGS__,VI3,VI2)(__VA_ARGS__)
#define VPI(name,size) vc<pi> name(size);rep(i_##name,size)input(name[i_##name].a,name[i_##name].b);
#define VVI(name,sizeN,sizeM) vvi name(sizeN,vi(sizeM));\
rep(i_##name,sizeN)rep(j_##name,sizeM)input(name[i_##name][j_##name]);
#define VS(name,size) vc<string> name(size);rep(i_##name,size)input(name[i_##name]);
#define VMI(name,size) vc<mint> name(size);rep(i_##name,size){INT(tmp_##name);name[i_##name]=tmp_##name;};
#define overload5(a,b,c,d,e,f,...) f
#define VVC4(type,name,sizeN,sizeM) vvc<type> name(sizeN,vc<type>(sizeM));
#define VVC5(type,name,sizeN,sizeM,ini) vvc<type> name(sizeN,vc<type>(sizeM,ini));
#define VVC(...) overload5(__VA_ARGS__,VVC5,VVC4)(__VA_ARGS__)
template<class T>
T vvvc(T v){
return v;
}
template<class T,class...Args>
auto vvvc(int n,T v,Args...args){
return vector(n,vvvc(v,args...));
}
template<int i,class T>
void print_tuple(ostream&,const T&){
}
template<int i,class T,class H,class ...Args>
void print_tuple(ostream&os,const T&t){
if(i)os<<",";
os<<get<i>(t);
print_tuple<i+1,T,Args...>(os,t);
}
template<class ...Args>
ostream& operator<<(ostream&os,const tuple<Args...>&t){
os<<"{";
print_tuple<0,tuple<Args...>,Args...>(os,t);
return os<<"}";
}
void printsuc(int suc){
#ifdef USE_FAST_IO
if(suc==1)pr.write('\n');
if(suc==2)pr.write(' ');
#else
if(suc==1){
if(dbg)cout<<endl;
else{
#ifdef LOCAL
cout<<endl;
#else
cout<<"\n";
#endif
}
}
if(suc==2)
cout<<" ";
#endif
}
template<class t>
void print_single(t x,int suc=1){
#ifdef USE_FAST_IO
pr.write(x);
#else
cout<<x;
#endif
printsuc(suc);
}
template<class t,class u>
void print_single(const pair<t,u>&p,int suc=1){
print_single(p.a,2);
print_single(p.b,suc);
}
template<class T>
void print_single(const vector<T>&v,int suc=1){
rep(i,v.size())
print_single(v[i],i==int(v.size())-1?3:2);
printsuc(suc);
}
template<class T,size_t N>
void print_single(const array<T,N>&v,int suc=1){
rep(i,N)
print_single(v[i],i==int(N)-1?3:2);
printsuc(suc);
}
template<class T>
void print(const T&t){
print_single(t);
}
template<class T,class ...Args>
void print(const T&t,const Args&...args){
print_single(t,2);
print(args...);
}
template<class T>
void printvv(const vvc<T>&vs){
for(const auto&row:vs)print(row);
}
string readString(){
string s;
cin>>s;
return s;
}
template<class T>
T sq(const T& t){
return t*t;
}
void YES(bool ex=true){
cout<<"YES\n";
if(ex)exit(0);
#ifdef LOCAL
cout.flush();
#endif
}
void NO(bool ex=true){
cout<<"NO\n";
if(ex)exit(0);
#ifdef LOCAL
cout.flush();
#endif
}
void Yes(bool ex=true){
cout<<"Yes\n";
if(ex)exit(0);
#ifdef LOCAL
cout.flush();
#endif
}
void No(bool ex=true){
cout<<"No\n";
if(ex)exit(0);
#ifdef LOCAL
cout.flush();
#endif
}
//#define CAPITAL
/*
void yes(bool ex=true){
#ifdef CAPITAL
cout<<"YES"<<"\n";
#else
cout<<"Yes"<<"\n";
#endif
if(ex)exit(0);
#ifdef LOCAL
cout.flush();
#endif
}
void no(bool ex=true){
#ifdef CAPITAL
cout<<"NO"<<"\n";
#else
cout<<"No"<<"\n";
#endif
if(ex)exit(0);
#ifdef LOCAL
cout.flush();
#endif
}*/
void possible(bool ex=true){
#ifdef CAPITAL
cout<<"POSSIBLE"<<"\n";
#else
cout<<"Possible"<<"\n";
#endif
if(ex)exit(0);
#ifdef LOCAL
cout.flush();
#endif
}
void impossible(bool ex=true){
#ifdef CAPITAL
cout<<"IMPOSSIBLE"<<"\n";
#else
cout<<"Impossible"<<"\n";
#endif
if(ex)exit(0);
#ifdef LOCAL
cout.flush();
#endif
}
constexpr ll ten(int n){
return n==0?1:ten(n-1)*10;
}
const ll infLL=LLONG_MAX/3;
#ifdef int
const int inf=infLL;
#else
const int inf=INT_MAX/2-100;
#endif
int topbit(signed t){
return t==0?-1:31-__builtin_clz(t);
}
int topbit(ll t){
return t==0?-1:63-__builtin_clzll(t);
}
int topbit(ull t){
return t==0?-1:63-__builtin_clzll(t);
}
int botbit(signed a){
return a==0?32:__builtin_ctz(a);
}
int botbit(ll a){
return a==0?64:__builtin_ctzll(a);
}
int botbit(ull a){
return a==0?64:__builtin_ctzll(a);
}
int popcount(signed t){
return __builtin_popcount(t);
}
int popcount(ll t){
return __builtin_popcountll(t);
}
int popcount(ull t){
return __builtin_popcountll(t);
}
int bitparity(ll t){
return __builtin_parityll(t);
}
bool ispow2(int i){
return i&&(i&-i)==i;
}
ll mask(int i){
return (ll(1)<<i)-1;
}
ull umask(int i){
return (ull(1)<<i)-1;
}
ll minp2(ll n){
if(n<=1)return 1;
else return ll(1)<<(topbit(n-1)+1);
}
bool inc(int a,int b,int c){
return a<=b&&b<=c;
}
template<class S> void mkuni(S&v){
sort(all(v));
v.erase(unique(all(v)),v.ed);
}
template<class t> bool isuni(vc<t> v){
int s=si(v);
mkuni(v);
return si(v)==s;
}
bool isperm(const vi&p){
int n=si(p);
vc<bool> used(n);
for(auto v:p){
if(!inc(0,v,n-1))return false;
if(used[v])return false;
used[v]=true;
}
return true;
}
template<class t>
void myshuffle(vc<t>&a){
rep(i,si(a))swap(a[i],a[rand_int(0,i)]);
}
template<class S,class u>
int lwb(const S&v,const u&a){
return lower_bound(all(v),a)-v.bg;
}
template<class t,class u>
bool bis(const vc<t>&v,const u&a){
return binary_search(all(v),a);
}
//VERIFY: yosupo
//KUPC2017J
//AOJDSL1A
//without rank
struct unionfind{
vi p,s;
int c;
unionfind(int n):p(n,-1),s(n,1),c(n){}
void clear(){
fill(all(p),-1);
fill(all(s),1);
c=si(p);
}
int find(int a){
return p[a]==-1?a:(p[a]=find(p[a]));
}
//set b to a child of a
bool unite(int a,int b){
a=find(a);
b=find(b);
if(a==b)return false;
p[b]=a;
s[a]+=s[b];
c--;
return true;
}
bool same(int a,int b){
return find(a)==find(b);
}
int sz(int a){
return s[find(a)];
}
};
vvc<int> readGraph(int n,int m){
vvc<int> g(n);
rep(i,m){
int a,b;
cin>>a>>b;
//sc.read(a,b);
a--;b--;
g[a].pb(b);
g[b].pb(a);
}
return g;
}
vvc<int> rand_tree(int n){
vvc<int> t(n);
unionfind uf(n);
while(uf.c>1){
int a=rand_int(n);
int b=rand_int(n);
if(uf.unite(a,b)){
t[a].pb(b);
t[b].pb(a);
}
}
return t;
}
vvc<int> readTree(int n){
if(dbg){
return rand_tree(n);
}else{
return readGraph(n,n-1);
}
}
vi readRooted(int n){
assert(!dbg);
vi par(n,-1);
rng(i,1,n){
input(par[i]);
par[i]--;
assert(inc(0,par[i],i-1));
}
return par;
}
void printTree(const vvc<int> t){
int n=si(t);
int degsum=0;
rep(i,n)degsum+=si(t[i]);
if(degsum==n-1){
//directed
rep(i,si(t))for(auto j:t[i]){
print(i+1,j+1);
}
}else if(degsum==2*(n-1)){
//undirected
rep(i,si(t))for(auto j:t[i])if(i<j){
print(i+1,j+1);
}
}else{
assert(false);
}
}
template<class t>
vc<t> presum(const vc<t>&a){
vc<t> s(si(a)+1);
rep(i,si(a))s[i+1]=s[i]+a[i];
return s;
}
vc<ll> presum(const vi&a){
vc<ll> s(si(a)+1);
rep(i,si(a))s[i+1]=s[i]+a[i];
return s;
}
//BIT で数列を管理するときに使う (CF850C)
template<class t>
vc<t> predif(vc<t> a){
gnr(i,1,si(a))a[i]-=a[i-1];
return a;
}
template<class t>
vvc<ll> imos(const vvc<t>&a){
int n=si(a),m=si(a[0]);
vvc<ll> b(n+1,vc<ll>(m+1));
rep(i,n)rep(j,m)
b[i+1][j+1]=b[i+1][j]+b[i][j+1]-b[i][j]+a[i][j];
return b;
}
//verify してないや
void transvvc(int&n,int&m){
swap(n,m);
}
template<class t,class... Args>
void transvvc(int&n,int&m,vvc<t>&a,Args&...args){
assert(si(a)==n);
vvc<t> b(m,vi(n));
rep(i,n){
assert(si(a[i])==m);
rep(j,m)b[j][i]=a[i][j];
}
a.swap(b);
transvvc(n,m,args...);
}
//CF854E
void rotvvc(int&n,int&m){
swap(n,m);
}
template<class t,class... Args>
void rotvvc(int&n,int&m,vvc<t>&a,Args&...args){
assert(si(a)==n);
vvc<t> b(m,vi(n));
rep(i,n){
assert(si(a[i])==m);
rep(j,m)b[m-1-j][i]=a[i][j];
}
a.swap(b);
rotvvc(n,m,args...);
}
//ソートして i 番目が idx[i]
//CF850C
template<class t>
vi sortidx(const vc<t>&a){
int n=si(a);
vi idx(n);iota(all(idx),0);
sort(all(idx),[&](int i,int j){return a[i]<a[j];});
return idx;
}
//vs[i]=a[idx[i]]
//例えば sortidx で得た idx を使えば単にソート列になって返ってくる
//CF850C
template<class t>
vc<t> a_idx(const vc<t>&a,const vi&idx){
int n=si(a);
assert(si(idx)==n);
vc<t> vs(n);
rep(i,n)vs[i]=a[idx[i]];
return vs;
}
//CF850C
vi invperm(const vi&p){
int n=si(p);
vi q(n);
rep(i,n)q[p[i]]=i;
return q;
}
template<class t,class s=t>
s SUM(const vc<t>&a){
return accumulate(all(a),s(0));
}
template<class t,size_t K,class s=t>
s SUM(const array<t,K>&a){
return accumulate(all(a),s(0));
}
template<class t>
t MAX(const vc<t>&a){
return *max_element(all(a));
}
template<class t>
pair<t,int> MAXi(const vc<t>&a){
auto itr=max_element(all(a));
return mp(*itr,itr-a.bg);
}
template<class A>
auto MIN(const A&a){
return *min_element(all(a));
}
template<class t>
pair<t,int> MINi(const vc<t>&a){
auto itr=min_element(all(a));
return mp(*itr,itr-a.bg);
}
vi vid(int n){
vi res(n);iota(all(res),0);
return res;
}
template<class S>
void soin(S&s){
sort(all(s));
}
template<class S,class F>
void soin(S&s,F&&f){
sort(all(s),forward<F>(f));
}
template<class S>
S soout(S s){
soin(s);
return s;
}
template<class S>
void rein(S&s){
reverse(all(s));
}
template<class S>
S reout(S s){
rein(s);
return s;
}
template<class t,class u>
pair<t,u>&operator+=(pair<t,u>&a,pair<t,u> b){
a.a+=b.a;a.b+=b.b;return a;}
template<class t,class u>
pair<t,u>&operator-=(pair<t,u>&a,pair<t,u> b){
a.a-=b.a;a.b-=b.b;return a;}
template<class t,class u>
pair<t,u> operator+(pair<t,u> a,pair<t,u> b){return mp(a.a+b.a,a.b+b.b);}
template<class t,class u>
pair<t,u> operator-(pair<t,u> a,pair<t,u> b){return mp(a.a-b.a,a.b-b.b);}
template<class t,class u,class v>
pair<t,u>&operator*=(pair<t,u>&a,v b){
a.a*=b;a.b*=b;return a;}
template<class t,class u,class v>
pair<t,u> operator*(pair<t,u> a,v b){return a*=b;}
template<class t,class u>
pair<t,u> operator-(pair<t,u> a){return mp(-a.a,-a.b);}
namespace std{
template<class t,class u>
istream&operator>>(istream&is,pair<t,u>&a){
return is>>a.a>>a.b;
}
}
template<class t,size_t n>
array<t,n>&operator+=(array<t,n>&a,const array<t,n>&b){
rep(i,n)a[i]+=b[i];
return a;
}
template<class t,size_t n>
array<t,n>&operator-=(array<t,n>&a,const array<t,n>&b){
rep(i,n)a[i]-=b[i];
return a;
}
template<class t,size_t n,class v>
array<t,n>&operator*=(array<t,n>&a,v b){
rep(i,n)a[i]*=b;
return a;
}
template<class t,size_t n>
array<t,n> operator+(array<t,n> a,const array<t,n>&b){return a+=b;}
template<class t,size_t n>
array<t,n> operator-(array<t,n> a,const array<t,n>&b){return a-=b;}
template<class t,size_t n,class v>
array<t,n> operator*(array<t,n> a,v b){return a*=b;}
template<class t>
t gpp(vc<t>&vs){
assert(si(vs));
t res=move(vs.back());
vs.pop_back();
return res;
}
template<class t,class u>
void pb(vc<t>&a,const vc<u>&b){
a.insert(a.ed,all(b));
}
template<class t,class...Args>
vc<t> cat(vc<t> a,Args&&...b){
(pb(a,forward<Args>(b)),...);
return a;
}
template<class t,class u>
vc<t>& operator+=(vc<t>&a,u x){
for(auto&v:a)v+=x;
return a;
}
template<class t,class u>
vc<t> operator+(vc<t> a,u x){
return a+=x;
}
template<class t>
vc<t>& operator+=(vc<t>&a,const vc<t>&b){
a.resize(max(si(a),si(b)));
rep(i,si(b))a[i]+=b[i];
return a;
}
template<class t>
vc<t> operator+(const vc<t>&a,const vc<t>&b){
vc<t> c(max(si(a),si(b)));
rep(i,si(a))c[i]+=a[i];
rep(i,si(b))c[i]+=b[i];
return c;
}
template<class t,class u>
vc<t>& operator-=(vc<t>&a,u x){
for(auto&v:a)v-=x;
return a;
}
template<class t,class u>
vc<t> operator-(vc<t> a,u x){
return a-=x;
}
template<class t>
vc<t>& operator-=(vc<t>&a,const vc<t>&b){
a.resize(max(si(a),si(b)));
rep(i,si(b))a[i]-=b[i];
return a;
}
/*
template<class t>
vc<t> operator-(const vc<t>&a,const vc<t>&b){
vc<t> c(max(si(a),si(b)));
rep(i,si(a))c[i]+=a[i];
rep(i,si(b))c[i]-=b[i];
return c;
}
*/
template<class t,class u>
vc<t>& operator*=(vc<t>&a,u x){
for(auto&v:a)v*=x;
return a;
}
template<class t,class u>
vc<t> operator*(vc<t> a,u x){
return a*=x;
}
template<class t,class u>
vc<t>& operator/=(vc<t>&a,u x){
for(auto&v:a)v/=x;
return a;
}
template<class t,class u>
vc<t> operator/(vc<t> a,u x){
return a/=x;
}
template<class t>
vc<t>& operator<<=(vc<t>&a,int k){
assert(k>=0);
a.insert(a.bg,k,t(0));
return a;
}
template<class t>
vc<t> operator<<(vc<t> a,int k){
return a<<=k;
}
template<class t>
vc<t>& operator>>=(vc<t>&a,int k){
if(si(a)<=k)a.clear();
else a.erase(a.bg,a.bg+k);
return a;
}
template<class t>
vc<t> operator>>(vc<t> a,int k){
return a>>=k;
}
template<class t,class u>
void remval(vc<t>&a,const u&v){
a.erase(remove(all(a),v),a.ed);
}
//消した要素の個数を返してくれる
//UCUP 2-8-F
template<class t,class F>
int remif(vc<t>&a,F f){
auto itr=remove_if(all(a),f);
int res=a.ed-itr;
a.erase(itr,a.ed);
return res;
}
template<class t>
void rempos(vc<t>&a,int i){
assert(inc(0,i,si(a)-1));
a.erase(a.bg+i);
}
template<class VS,class u>
void fila(VS&vs,const u&a){
fill(all(vs),a);
}
template<class t,class u>
int findid(const vc<t>&vs,const u&a){
auto itr=find(all(vs),a);
if(itr==vs.ed)return -1;
else return itr-vs.bg;
}
template<class t>
void rtt(vc<t>&vs,int i){
rotate(vs.bg,vs.bg+i,vs.ed);
}
//Multiuni2023-8 C
//f(lw)=false,...,f(n-1)=false,f(n)=true,...,f(up)=true,
//のときに n を返す
template<class F>
int find_min_true(int lw,int up,F f){
while(up-lw>1){
const int mid=(lw+up)/2;
if(f(mid))up=mid;
else lw=mid;
}
return up;
}
//f(lw)=true,f(up)=false
template<class F>
int find_max_true(int lw,int up,F f){
while(up-lw>1){
const int mid=(lw+up)/2;
if(f(mid))lw=mid;
else up=mid;
}
return lw;
}
template<class t> using pqmin=priority_queue<t,vc<t>,greater<t>>;
template<class t> using pqmax=priority_queue<t>;
using T=tuple<int,int,int>;
//N() が単位元
//VERIFY: yosupo
//CF407E
template<class N>
struct segtree{
vc<N> x;
int n,s;
segtree(){}
template<class t>
segtree(const vc<t>&a){
n=a.size();
s=1;
while(s<n){s*=2;}
x.resize(s*2);
rep(i,n)
x[s+i]=N(a[i]);
gnr(i,1,s)
x[i]=N::merge(x[i*2],x[i*2+1]);
}
//NOT Verified
segtree(int nn){
resize(nn);
}
void resize(int nn){
n=nn;
s=1;
while(s<n){s*=2;}
x.assign(s*2,N());
gnr(i,1,s)
x[i]=N::merge(x[i*2],x[i*2+1]);
}
template<class t>
void init(const vc<t>&a){
n=a.size();
s=1;
while(s<n){s*=2;}
x.resize(s*2);
rep(i,n)
x[s+i]=N(a[i]);
rng(i,n,s)
x[s+i]=N();
gnr(i,1,s)
x[i]=N::merge(x[i*2],x[i*2+1]);
}
void clear(){
rep(i,n)
x[s+i]=N();
gnr(i,1,s)
x[i]=N::merge(x[i*2],x[i*2+1]);
}
N point_get(int i){
assert(inc(0,i,n-1));
return x[i+s];
}
void point_set(int i,const N&t){
assert(inc(0,i,n-1));
i+=s;
x[i]=t;
while(i>>=1)x[i]=N::merge(x[i*2],x[i*2+1]);
}
void point_merge(int i,const N&t){
assert(inc(0,i,n-1));
i+=s;
x[i]=N::merge(x[i],t);
while(i>>=1)x[i]=N::merge(x[i*2],x[i*2+1]);
}
template<class F,class...Args>
void point_change(int i,F f,Args&&...args){
assert(inc(0,i,n-1));
i+=s;
(x[i].*f)(forward<Args>(args)...);
while(i>>=1)x[i]=N::merge(x[i*2],x[i*2+1]);
}
N composite(int b,int e){
assert(0<=b&&b<=e&&e<=n);
N lf,rt;
for(int l=b+s,r=e+s;l<r;l>>=1,r>>=1){
if (l&1){
lf=N::merge(lf,x[l]);
l++;
}
if (r&1){
r--;
rt=N::merge(x[r],rt);
}
}
return N::merge(lf,rt);
}
N getall(){
return x[1];
}
//used in namori-bisect
template <class F,class... Args>
pair<int,N> max_right_withinit(int l,N sm,F f,Args&&... args){
assert((sm.*f)(forward<Args>(args)...));
assert(0<=l&&l<=n);
if(l==n)return mp(n,sm);
l+=s;
assert((sm.*f)(forward<Args>(args)...));
do {
while (l % 2 == 0) l >>= 1;
if (!(N::merge(sm,x[l]).*f)(forward<Args>(args)...)){
while (l < s) {
l = (2 * l);
N tmp=N::merge(sm,x[l]);
if ((tmp.*f)(forward<Args>(args)...)) {
sm = tmp;
l++;
}
}
return mp(l - s,sm);
}
sm = N::merge(sm, x[l]);
l++;
} while ((l & -l) != l);
return mp(n,sm);
}
//UCUP-2-22-K
template <class F,class... Args>
pair<int,N> min_left_withinit(int r,N sm,F f,Args&&... args){
assert((sm.*f)(forward<Args>(args)...));
assert(0<=r&&r<=n);
if(r==0)return mp(0,sm);
r+=s;
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!(N::merge(x[r],sm).*f)(forward<Args>(args)...)) {
while (r < s) {
r = (2 * r + 1);
N tmp=N::merge(x[r],sm);
if ((tmp.*f)(forward<Args>(args)...)) {
sm = tmp;
r--;
}
}
return mp(r + 1 - s,sm);
}
sm = N::merge(x[r], sm);
} while ((r & -r) != r);
return mp(0,sm);
}
//UTPC2020E
//n 超えるかもしれない
template <class F,class... Args>
pair<int,N> max_right(int l,F f,Args&&... args){
return max_right_withinit(l,N(),f,forward<Args>(args)...);
}
//UTPC2020E
template <class F,class... Args>
pair<int,N> min_left(int r,F f,Args&&... args){
return min_left_withinit(r,N(),f,forward<Args>(args)...);
}
//行列とか乗せて必要なのはベクトルとの積，みたいなときに使える？
//CF Goodbye 2016 E
//CF 896 F
template<class F,class T,class... Args>
T accumulate(int l,int r,F f,T t,Args&&... args) {
assert(0<=l&&l<=r&&r<=n);
static int buf[2][30];
int cnt[2]{};
for(l+=s,r+=s;l<r;l>>=1,r>>=1){
if(l&1)buf[0][cnt[0]++]=l;
if(r&1)buf[1][cnt[1]++]=r-1;
l++;
}
rep(i,cnt[0])t=(x[buf[0][i]].*f)(t,forward<Args>(args)...);
per(i,cnt[1])t=(x[buf[1][i]].*f)(t,forward<Args>(args)...);
return t;
}
};
//i->par[i] と遷移すると raw[i] かかるとする
//i->...->j までの raw を全部 composite したものを考える
//これが ok な最大の j というものを取ってくる
//そこまでの composite も取ってくる
//サイクルにも対応!
//高々 upto 回までの遷移を行う
//stress-tested! (others に入れた)
template<class N>
struct namori_bisect{
vi par;
const int n;
vc<N> acc;
vi sub,head,pos,sop;
segtree<N> seg;
template<class t>
vc<N> init(const vc<t>&raw){
vvc<int> g(n);
rep(i,n)if(par[i]!=-1)g[par[i]].pb(i);
vi deg(n);
rep(i,n)deg[i]=si(g[i]);
vi q;
rep(i,n)if(deg[i]==0)q.pb(i);
while(si(q)){
int v=gpp(q);
if(par[v]!=-1){
sub[par[v]]+=sub[v];
if(--deg[par[v]]==0)q.pb(par[v]);
}
}
int ord=0;
vc<N> res(n);
auto dfs=[&](auto self,int v,int h)->void{
head[v]=h;
if(v==h) acc[v]=raw[v];
else acc[v]=N::merge(raw[v],acc[par[v]]);
if(si(g[v])){
rng(i,1,si(g[v]))
if(sub[g[v][0]]<sub[g[v][i]])
swap(g[v][0],g[v][i]);
rng(i,1,si(g[v]))
self(self,g[v][i],g[v][i]);
self(self,g[v][0],h);
}
pos[v]=ord++;
res[pos[v]]=raw[v];
sop[pos[v]]=v;
};
auto work=[&](int root){
dfs(dfs,root,root);
};
rep(i,n)if(par[i]==-1){
for(auto r:g[i]){
work(r);
}
}
rep(i,n)if(deg[i]>0){
int x=i;
while(1){
deg[x]=0;
int y=par[x];
if(y!=i){
sub[y]+=sub[x];
x=y;
}else break;
}
remval(g[i],x);
work(x);
par[x]=n+i;
}
res.resize(ord);
return res;
}
template<class t>
namori_bisect(const vi&pp,const vc<t>&raw):par(pp),n(si(par)),
acc(n),sub(n,1),head(n,-1),pos(n,-1),sop(n,-1),
seg(init(raw)){}
//v から start してどの長さまで遷移できるか
//steps,last_vertex,data
template <class F,class... Args>
tuple<int,int,N> max_len_withinit(int v,int upto,N sm,F f,Args&&... args){
assert(inc(0,v,n-1));
assert((sm.*f)(forward<Args>(args)...));
int step=0;
auto adv=[&](int u){
assert(inc(0,u,upto));
assert(inc(0,v,n-1));
assert(inc(0,u,pos[head[v]]-pos[v]));
v=sop[pos[v]+u];
step+=u;
upto-=u;
};
while(v<n&&par[v]!=-1&&upto>0){
int h=head[v];
int dist=pos[h]-pos[v]+1;
if(upto<dist){//definitely ends here
auto [u,z]=seg.max_right_withinit(pos[v],sm,f,forward<Args>(args)...);
if(pos[v]+upto<u){
sm=N::merge(sm,seg.composite(pos[v],pos[v]+upto));
adv(upto);
}else{
sm=z;
adv(u-pos[v]);
}
break;
}else{
N tmp=N::merge(sm,acc[v]);
if((tmp.*f)(forward<Args>(args)...)){
adv(dist-1);
v=par[v];
step++;
upto--;
sm=tmp;
}else{
auto [u,z]=seg.max_right_withinit(pos[v],sm,f,forward<Args>(args)...);
sm=z;
adv(u-pos[v]);
break;
}
}
}
assert(v!=-1);
if(upto==0||v<n){return mt(step,v%n,sm);}
v-=n;
int dist=0;
N sc;
{
for(int x=v;x!=v+n;){
int h=head[x];
dist+=pos[h]-pos[x]+1;
sc=N::merge(sc,acc[x]);
x=par[h];
}
}
static vc<N> cyc; cyc.clear();
cyc.pb(sc);
rep(i,100){
if((N::merge(sm,cyc[i]).*f)(forward<Args>(args)...)&&(dist<<i)<=upto){
cyc.pb(N::merge(cyc.back(),cyc.back()));
}else break;
}
per(i,si(cyc)){
N tmp=N::merge(sm,cyc[i]);
if((tmp.*f)(forward<Args>(args)...)&&(dist<<i)<=upto){
sm=tmp;
step+=dist<<i;
upto-=dist<<i;
}
}
auto [rstep,rv,rsm]=max_len_withinit(v,upto,sm,f,forward<Args>(args)...);
rstep+=step;
return mt(rstep,rv,rsm);
}
template <class F,class... Args>
tuple<int,int,N> max_len(int v,F f,Args&&... args){
return max_len_withinit(v,inf,N(),f,forward<Args>(args)...);
}
};
//point2d_general,wavelet 等で使用
template<class t>
struct vec2d{
int n,s,used;
vc<t*> x;
vi lens;
unique_ptr<t[]> p;
vec2d(int nn,int ss):n(nn),s(ss),used(0),x(n,nullptr),lens(n),p(new t[s]){}
void init(int i,int len){
assert(lens[i]==0);
assert(len>=0);
x[i]=p.get()+used;
lens[i]=len;
used+=len;
assert(used<=s);
}
t* operator[](int i){
assert(inc(0,i,n-1));
return x[i];
}
};
//pos と言ったときには元の数列での位置を意味する．
//id と言ったときにはソート済み列での位置を意味する．
template<class t,class V>
struct wavelet{
const vc<t> a;
const vc<V> wei;
const int n,L,s;
vc<t> st;
vi i2p;
vec2d<int> pos;
vec2d<pi> cut;
vec2d<V> sum;
void presum(int len,int*b,V*z){
rep(i,len)z[i+1]=z[i]+wei[b[i]];
}
void merge_with_cut(int ls,int *l,int rs,int *r,int *b,pi *c){
c[0]=pi(0,0);
int x=0,y=0;
rep(i,ls+rs){
bool usel=true;
if(x==ls||(y<rs&&l[x]>r[y]))usel=false;
if(usel)b[i]=l[x++];
else b[i]=r[y++];
c[i+1]=pi(x,y);
}
}
wavelet(const vc<t>&aa,const vc<V>&ww):a(aa),wei(ww),n(si(a)),L(topbit(max<int>(n-1,1))+1),s(1<<L),
st(n),i2p(n),pos(s*2,(L+1)*n),cut(s*2,L*n+s),sum(s*2,(L+1)*n+s*2)
{
{
iota(all(i2p),0);
stable_sort(all(i2p),[&](int i,int j){return a[i]<a[j];});
rep(i,n)st[i]=a[i2p[i]];
rep(i,n){
pos.init(s+i,1);
pos[s+i][0]=i2p[i];
}
}
gnr(i,1,s){
int ls=pos.lens[i*2];
int rs=pos.lens[i*2+1];
pos.init(i,ls+rs);
cut.init(i,ls+rs+1);
merge_with_cut(ls,pos[i*2],rs,pos[i*2+1],pos[i],cut[i]);
}
rng(i,1,s*2){
sum.init(i,pos.lens[i]+1);
presum(pos.lens[i],pos[i],sum[i]);
}
}
pi lrL(int i,int l,int r){
return pi(cut[i][l].a,cut[i][r].a);
}
pi lrR(int i,int l,int r){
return pi(cut[i][l].b,cut[i][r].b);
}
//kth-smallest value in a
t kth(int k){
assert(inc(0,k,n-1));
return st[k];
}
//value v 以上になる最初の id を返す
int lwbval(t v){
return lwb(st,v);
}
//id of kth-smallest value in [l,r)
int kthid(int l,int r,int k){
assert(0<=l&&l<=r&&r<=n);
assert(inc(0,k,r-l-1));
int i=1;
while(i<s){
auto [x,y]=lrL(i,l,r);
auto [z,w]=lrR(i,l,r);
if(y-x<=k){
k-=y-x;
i=i*2+1;
l=z,r=w;
}else{
i=i*2;
l=x,r=y;
}
}
assert(k==0);
return i-s;
}
//value of kth-smallest value in [l,r)
t kthval(int l,int r,int k){
assert(0<=l&&l<=r&&r<=n);
return kth(kthid(l,r,k));
}
//positin [l,r) にある値のなかで，tar 以上の最小の id 返す
//ないなら S
int lwbid(int l,int r,int tar){
assert(0<=l&&l<=r&&r<=n);
assert(inc(0,tar,n));
if(tar==n)return s;
if(inc(l,i2p[tar],r-1))return tar;
tar+=s;
pi buf[30];
per(h,L){
int i=tar>>(h+1);
if((tar>>h)&1){
tie(l,r)=lrR(i,l,r);
}else{
buf[h]=lrR(i,l,r);
tie(l,r)=lrL(i,l,r);
}
}
rep(h,L)if(((tar>>h)&1)==0){
int i=(tar>>h)+1;
tie(l,r)=buf[h];
if(l==r)continue;
while(i<s){
auto [x,y]=lrL(i,l,r);
auto [z,w]=lrR(i,l,r);
if(x==y){
i=i*2+1;
l=z,r=w;
}else{
i=i*2;
l=x,r=y;
}
}
return i-s;
}
return s;
}
//position [l,r) にある値のなかで，id が tar 未満の個数を返す
int countid(int l,int r,int tar){
assert(0<=l&&l<=r&&r<=n);
assert(inc(0,tar,n));
if(tar==n)return r-l;
tar+=s;
int res=0;
per(h,L){
int i=tar>>(h+1);
if((tar>>h)&1){
auto [x,y]=lrL(i,l,r);
res+=y-x;
tie(l,r)=lrR(i,l,r);
}else{
tie(l,r)=lrL(i,l,r);
}
}
return res;
}
//position [l,r) にある値のなかで，value が val 未満の個数を返す
int countval(int l,int r,t val){
return countid(l,r,lwbval(val));
}
//position [l,r) にある値のなかで，value が [d,u) の個数を返す
int countval(int l,int r,t d,t u){
return countval(l,r,u)-countval(l,r,d);
}
//position [l,r) にある値のなかで，id が tar 未満の要素に紐付いた sum を返す
V sumid(int l,int r,int tar){
assert(0<=l&&l<=r&&r<=n);
assert(inc(0,tar,n));
if(tar==n)return sum[1][r]-sum[1][l];
tar+=s;
V res=0;
per(h,L){
int i=tar>>(h+1);
if((tar>>h)&1){
auto [x,y]=lrL(i,l,r);
res+=sum[i*2][y]-sum[i*2][x];
tie(l,r)=lrR(i,l,r);
}else{
tie(l,r)=lrL(i,l,r);
}
}
return res;
}
//position [l,r) にある値のなかで，value が val 未満の要素に紐付いた sum を返す
V sumval(int l,int r,t val){
return sumid(l,r,lwbval(val));
}
};
//平面上に点がたくさん (static)
//矩形クエリ
//stress-tested (without define int ll)
template<class V> //重み
struct wavelet_helper{
const int n;
vi xs,ys;
vc<V> ws;
wavelet<int,V> wv;
void init(vc<tuple<int,int,V>>xyw){
soin(xyw);
rep(i,n){
auto [x,y,w]=xyw[i];
xs[i]=x;
ys[i]=y;
ws[i]=w;
}
}
wavelet_helper(const vc<tuple<int,int,V>>&xyw):
n(si(xyw)),xs(n),ys(n),ws(n),
wv((init(xyw),ys),ws){}
//[l,r)*[-inf,y) 内の点の重みの総和
V rect_low(int l,int r,int y){
assert(l<=r);
l=lwb(xs,l);
r=lwb(xs,r);
return wv.sumval(l,r,y);
}
};
//[l,r)
//Yandex Finals 2024 C
void meld(vc<pi>&vs){
//soin(vs);
int s=0;
for(auto&[l,r]:vs){
if(s&&vs[s-1].b>=l){
chmax(vs[s-1].b,r);
}else{
vs[s++]={l,r};
}
}
vs.resize(s);
}
#ifdef LOCAL
int V=10;
#else
int V=ten(6)+1;
#endif
struct N{
int len;
ll cost;
N():len(0),cost(0){}
N(int a,ll b):len(a),cost(b){}
static N merge(const N&x,const N&y){
return N(x.len+y.len,x.cost+y.cost);
}
bool ok(int v){return len<=v;}
};
template<class HF,class VF>
struct UpperPath{
const int flip;
const int ward;
const vvc<pi>&blocks;
HF hff;
VF vff;
vi off;
int n;
vi par;
vc<N> val;
vc<pi> xys;
namori_bisect<N> z;
ll hf(int v,int l,int r){
if(ward){
v=V-v;
l=V-l;
r=V-r;
swap(l,r);
}
return flip?vff(v,l,r):hff(v,l,r);
}
ll vf(int v,int l,int r){
if(ward){
v=V-v;
l=V-l;
r=V-r;
swap(l,r);
}
return flip?hff(v,l,r):vff(v,l,r);
}
void init(){
off.resize(V+1);
rep(i,V)off[i+1]=off[i]+si(blocks[i]);
n=off[V];
par.resize(n,-1);
val.resize(n);
xys.resize(n);
rep(i,V)rep(j,si(blocks[i]))xys[off[i]+j]=pi(i+1,blocks[i][j].a);
rep(i,V){
rep(j,si(blocks[i])){
int k=-1;
if(i+1<V){
k=lwb(blocks[i+1],pi(blocks[i][j].a,-1));
if(k==si(blocks[i+1]))k=-1;
}
if(k!=-1){
int l=blocks[i][j].a,r=blocks[i+1][k].a;
int len=r-l+1;
int cost=vf(i+1,l,r)+hf(r,i+1,i+2);
par[off[i]+j]=off[i+1]+k;
val[off[i]+j]=N(len,cost);
}
}
}
}
UpperPath(int fl,int wa,const vvc<pi>&bb,HF hh,VF vv):
flip(fl),ward(wa),
blocks(bb),hff(hh),vff(vv),z((init(),par),val){}
tuple<int,int,ll> ask(int x,int y,int steps,bool calccost){
if(flip)swap(x,y);
if(ward){
x=V-x;
y=V-y;
}
auto hfc=[&](int v,int l,int r)->ll{
if(calccost){
return hf(v,l,r);
}else{
return 0;
}
};
auto vfc=[&](int v,int l,int r)->ll{
if(calccost){
return vf(v,l,r);
}else{
return 0;
}
};
ll cost=0;
auto advh=[&](int u){
cost+=hfc(y,x,x+u);
x+=u;
steps-=u;
};
auto advv=[&](int u){
cost+=vfc(x,y,y+u);
y+=u;
steps-=u;
};
int k=lwb(blocks[x],pi(y,-1));
if(k==si(blocks[x])||blocks[x][k].a-y>=steps){
advv(steps);
}else{
int start=off[x]+k;
advv(blocks[x][k].a-y);
advh(1);
auto [dummy,v,nd]=z.max_len(start,&N::ok,steps);
tie(x,y)=xys[v];
cost+=nd.cost;
steps-=nd.len;
advv(steps);
}
if(ward){
x=V-x;
y=V-y;
}
if(flip)swap(x,y);
return mt(x,y,cost);
}
};
void slv(){
INT(n,q);
VPI(xy,n);
if(dbg){
V=calc_random_limit()+2;
mkuni(xy);
n=si(xy);
}
vvc<pi> blocks[2][2];
rep(flip,2){
vvc<pi> obs(V);
for(auto[x,y]:xy){
obs[x].eb(y,y+1);
}
rep(x,V)soin(obs[x]);
rep(_,2){
rep(x,V)if(si(obs[x])){
for(auto&[l,r]:obs[x]){
int i=lwb(obs[x-1],pi(r+1,-1));
if(i>0)chmax(r,obs[x-1][i-1].b);
}
meld(obs[x]);
}
rein(obs);
for(auto&ls:obs){
rein(ls);
for(auto&[l,r]:ls){
l=V-l;
r=V-r;
swap(l,r);
}
}
}
rep(ward,2){
blocks[flip][ward]=obs;
rein(obs);
for(auto&ls:obs){
rein(ls);
for(auto&[l,r]:ls){
l=V-l;
r=V-r;
swap(l,r);
}
}
}
for(auto&[x,y]:xy)swap(x,y);
}
dmp(blocks[0][0]);
dmp(blocks[1][0]);
dmp(blocks[1][1]);
vi freecnt(V,V);
rep(i,V)for(auto [l,r]:blocks[0][0][i])
freecnt[i]-=r-l;
vc<ll> freesum=presum(freecnt);
vc<tuple<int,int,ll>> bottoms;
rep(i,V)for(auto [l,r]:blocks[0][0][i])
bottoms.eb(i,l,r-l);
wavelet_helper<ll> wh(bottoms);
auto belowgood=[&](int h,int l,int r){
assert(inc(0,h,V));
assert(0<=l&&l<=r&&r<=V);
ll res=ll(h)*(r-l);
res-=wh.rect_low(l,r,h);
return res;
};
auto abovegood=[&](int h,int l,int r){
return (freesum[r]-freesum[l])-belowgood(h,l,r);
};
auto zerogood=[&](int,int,int){return 0;};
UpperPath U(0,0,blocks[0][0],belowgood,zerogood);
UpperPath D(0,1,blocks[0][1],abovegood,zerogood);
UpperPath R(1,0,blocks[1][0],abovegood,zerogood);
UpperPath L(1,1,blocks[1][1],belowgood,zerogood);
auto inside=[&](int x,int y){
int k=lwb(blocks[0][0][x],pi(y+1,-1));
return k>0&&y<blocks[0][0][x][k-1].b;
};
auto query=[&](int sx,int sy,int tx,int ty)->ll{
if(inside(sx,sy)||inside(tx,ty)){
return 0;
}else{
tx++;
ty++;
int dist=tx-sx+ty-sy;
{
auto [x,y,dummy]=U.ask(sx,sy,dist,false);
if(tx<x){
return 0;
}
}
{
auto [x,y,dummy]=R.ask(sx,sy,dist,false);
if(x<tx){
return 0;
}
}
{
auto [x,y,dummy]=L.ask(tx,ty,dist,false);
if(sx<x){
return 0;
}
}
{
auto [x,y,dummy]=D.ask(tx,ty,dist,false);
if(x<sx){
return 0;
}
}
ll ans=0;
ans+=[&](){
int l=-1,r=dist+1;
while(1){
int m=(l+r)/2;
assert(l<m&&m<r);
auto [x,y,tmp1]=U.ask(sx,sy,m,false);
auto [u,v,tmp2]=L.ask(tx,ty,dist-m,false);
if(x==u){
return
get<2>(U.ask(sx,sy,m,true))+
get<2>(L.ask(tx,ty,dist-m,true));
}else if(x<u){
r=m;
}else{
l=m;
}
}
}();
ans+=[&](){
int l=-1,r=dist+1;
while(1){
int m=(l+r)/2;
assert(l<m&&m<r);
auto [x,y,tmp1]=R.ask(sx,sy,m,false);
auto [u,v,tmp2]=D.ask(tx,ty,dist-m,false);
if(x==u){
return
get<2>(R.ask(sx,sy,m,true))+
get<2>(D.ask(tx,ty,dist-m,true));
}else if(x>u){
r=m;
}else{
l=m;
}
}
}();
ans-=(freesum[tx]-freesum[sx]);
return max<ll>(ans,0);
}
};
rep(_,q){
INT(sx,sy,tx,ty);
if(dbg){
if(sx>tx)swap(sx,tx);
if(sy>ty)swap(sy,ty);
}
ll ans=query(sx,sy,tx,ty);
if(dbg){
VVC(int,dame,V,V);
for(auto [x,y]:xy)dame[x][y]=1;
auto updA=[&](int u,int v){
VVC(int,dp,V,V);
dp[u][v]=1;
rep(i,V)rep(j,V){
if(dame[i][j])dp[i][j]=0;
if(dp[i][j]){
if(i+1<V)dp[i+1][j]|=dp[i][j];
if(j+1<V)dp[i][j+1]|=dp[i][j];
}
}
rep(i,V)rep(j,V)if(!dp[i][j])
dame[i][j]=true;
};
auto updB=[&](int u,int v){
VVC(int,dp,V,V);
dp[u][v]=1;
per(i,V)per(j,V){
if(dame[i][j])dp[i][j]=0;
if(dp[i][j]){
if(i-1>=0)dp[i-1][j]|=dp[i][j];
if(j-1>=0)dp[i][j-1]|=dp[i][j];
}
}
rep(i,V)rep(j,V)if(!dp[i][j])
dame[i][j]=true;
};
updA(0,0);
updB(V-1,V-1);
updA(sx,sy);
updB(tx,ty);
int god=0;
rng(x,sx,tx+1)rng(y,sy,ty+1)if(!dame[x][y])god++;
if(god!=ans){
print(n,1);
for(auto [x,y]:xy)print(x,y);
print(sx,sy,tx,ty);
print(god,ans);
assert(false);
}
}else{
print(ans);
}
}
}
signed main(signed argc,char*argv[]){
if(argc>1&&strcmp(argv[1],"D")==0)dbg=true;
cin.tie(0);
ios::sync_with_stdio(0);
cout<<fixed<<setprecision(20);
if(dbg){
while(1){
if(current_run_id%run_batch_size==0){
cerr<<"Current Run "<<current_run_id<<endl;
}
slv();
current_run_id++;
}
}else{
//INT(t);rep(_,t)
slv();
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 79ms
memory: 128512kb
input:
3 3 2 3 3 2 4 4 1 1 5 5 3 4 5 5 3 3 4 5
output:
20 4 0
result:
ok 3 number(s): "20 4 0"
Test #2:
score: 0
Accepted
time: 82ms
memory: 128516kb
input:
8 2 2 2 2 5 3 5 4 1 5 4 6 1 7 3 8 2 1 1 9 5 5 1 8 5
output:
28 11
result:
ok 2 number(s): "28 11"
Test #3:
score: 0
Accepted
time: 70ms
memory: 128340kb
input:
10 9 6 7 10 5 4 4 6 6 4 10 6 1 4 6 5 6 7 11 10 9 5 7 10 11 1 11 5 11 1 10 7 10 8 5 9 7 8 4 11 7 9 11 11 11 11 9 11 9 7 2 7 6 9 1 10 9
output:
20 5 0 6 15 3 1 5 0
result:
ok 9 numbers
Test #4:
score: 0
Accepted
time: 76ms
memory: 128484kb
input:
10 9 9 4 9 9 2 1 6 7 6 3 2 6 9 3 10 5 1 5 10 2 7 7 8 10 2 10 7 10 7 6 10 9 7 9 7 9 8 5 8 8 3 5 6 7 7 1 7 7 5 4 9 4 8 8 10 9
output:
8 6 13 1 4 0 7 0 4
result:
ok 9 numbers
Test #5:
score: 0
Accepted
time: 76ms
memory: 128560kb
input:
100 101 76 97 68 64 68 68 64 74 4 86 51 22 11 19 90 74 72 38 79 13 8 79 7 1 99 12 32 58 43 92 6 57 92 30 7 29 64 33 3 67 76 46 40 5 47 98 25 51 60 8 81 14 65 71 27 61 64 54 79 96 96 82 69 79 74 99 3 73 21 62 24 92 34 77 79 69 64 59 54 67 91 19 83 86 54 30 47 61 19 34 89 64 69 65 29 35 71 78 72 54 83...
output:
10 1048 780 389 54 419 0 341 768 270 107 110 14 129 173 965 49 23 619 129 625 47 1042 90 1263 117 1164 58 2508 1080 398 315 48 24 1625 2675 47 572 453 247 18 1113 30 1311 1694 9 1292 348 89 32 1102 26 528 84 152 33 190 61 991 16 198 2 707 9 303 4046 11 1741 1619 1556 436 51 1676 71 138 2678 502 180 ...
result:
ok 101 numbers
Test #6:
score: 0
Accepted
time: 79ms
memory: 128448kb
input:
100 101 98 24 98 51 60 82 41 51 71 45 12 18 64 68 25 69 44 27 93 3 10 12 5 7 60 10 42 42 75 53 55 67 14 95 19 93 91 26 72 16 10 79 54 32 60 41 13 53 14 24 10 21 79 83 35 93 93 26 3 65 29 64 11 91 14 27 56 16 94 71 70 55 9 95 94 95 96 23 17 86 19 51 55 61 84 14 21 56 30 4 43 32 22 37 35 56 69 80 52 3...
output:
1159 146 710 2231 112 96 547 2072 74 60 437 150 3 551 1132 0 0 27 1032 711 654 36 78 100 174 51 462 458 949 4417 36 48 308 29 1517 554 729 928 54 65 23 13 154 6 272 53 0 718 47 16 180 4406 49 1791 320 60 1884 120 3860 0 75 67 431 2 90 811 96 148 169 5 12 577 2114 16 408 497 716 63 35 219 5 150 36 50...
result:
ok 101 numbers
Test #7:
score: 0
Accepted
time: 79ms
memory: 128604kb
input:
1000 1000 449 587 786 695 472 659 506 210 399 915 440 445 845 927 825 641 911 968 977 492 470 151 610 442 960 466 805 970 753 123 469 879 656 541 315 610 830 148 226 612 643 832 808 374 310 895 30 477 82 496 154 35 82 907 234 326 555 880 569 940 207 619 658 812 511 827 57 813 568 30 439 410 410 99 8...
output:
27654 14243 78 47918 43131 1364 86355 398 916 121057 37902 142221 27571 6955 13918 13416 5931 92332 17183 203642 1019 156 33556 26777 23607 114610 49528 6402 258738 1404 57965 365677 2652 17592 63346 17474 261013 31678 540 15317 13566 232168 68911 17027 17736 12150 81418 4414 68071 1714 15298 20480 ...
result:
ok 1000 numbers
Test #8:
score: 0
Accepted
time: 72ms
memory: 128732kb
input:
1000 1000 710 466 349 78 453 408 244 925 747 186 249 4 436 550 380 563 649 365 326 206 255 158 983 500 246 624 842 889 835 747 996 820 78 112 752 290 661 116 461 545 791 490 206 582 994 78 33 856 182 666 433 162 864 28 717 277 360 550 150 35 835 317 797 741 129 723 50 846 736 470 206 942 863 382 74 ...
output:
65551 8465 89072 25493 150 371215 12661 8316 1188 78910 258056 72575 56027 23195 75423 467230 31951 460784 21512 38595 42008 124205 31219 24359 1160 188 421789 38651 34626 1511 339125 373149 26579 114227 53374 62780 24209 33855 93531 248496 44675 1203 109618 25991 96761 65091 299 6817 147628 52970 7...
result:
ok 1000 numbers
Test #9:
score: 0
Accepted
time: 991ms
memory: 219424kb
input:
100000 99999 983 852 575 13 543 878 755 288 401 928 655 124 711 939 694 279 550 707 563 715 29 364 411 960 911 939 729 514 92 863 913 440 776 683 709 994 780 847 441 142 837 692 233 141 422 989 732 933 875 454 767 871 624 631 469 841 958 481 18 116 333 674 394 720 811 544 32 689 813 499 267 581 511 ...
output:
445 57187 17483 0 346102 1622 0 12656 0 44039 22420 0 148090 0 0 4396 0 3461 65419 0 0 38719 46302 39652 0 8643 39061 26870 8392 0 0 11216 0 9478 2496 25239 52083 0 0 3307 424 6942 0 66032 46463 11474 0 1783 0 0 20412 54263 0 913 11852 20454 0 0 183098 6248 3576 0 0 0 6032 0 1792 0 0 0 1882 10468 0 ...
result:
ok 99999 numbers
Test #10:
score: 0
Accepted
time: 987ms
memory: 219232kb
input:
100000 99999 617 219 583 489 859 223 357 870 685 998 366 735 839 116 214 613 566 861 76 429 444 615 818 117 766 771 528 763 109 440 345 542 238 112 508 195 66 186 132 113 39 742 289 525 796 508 445 759 313 69 8 827 53 336 893 866 646 255 298 502 637 279 356 769 879 964 841 446 485 658 204 183 844 26...
output:
46658 254767 0 8058 0 0 0 46820 37579 0 55191 23213 49038 0 0 0 3545 0 0 11175 0 0 21654 0 0 21131 0 44062 6590 0 47242 34570 28399 1173 0 59768 20548 0 1 0 0 48023 182240 1325 0 2809 0 1183 0 0 0 0 0 0 11411 0 45567 27480 203594 0 56 3066 0 0 0 0 31788 0 542 0 4381 45175 26240 5598 201698 66755 477...
result:
ok 99999 numbers
Test #11:
score: -100
Wrong Answer
time: 1287ms
memory: 229208kb
input:
99999 100000 8444 363 6414 6013 7224 9013 1299 7338 6178 3758 9215 8820 2643 7453 7610 5729 7673 9202 5944 1896 5864 172 3517 6257 6986 4119 7283 4410 3770 8619 4825 1234 8900 7582 1310 1613 3966 6918 9434 604 7612 6079 933 4900 6630 817 9583 9313 5764 8132 2689 4128 8557 8976 1550 6794 8021 4031 45...
output:
271682 7750409 9197136 0 1505234 4944186 1147420 166115 34254692 16386047 0 130746 1315026 6905921 68312 35493 15625874 24355274 6974321 5858746 126192 3238570 2869775 26819097 4300645 2998708 3158360 1049228 770512 7455744 2094905 0 151603 12240 1065472 4678144 1000484 1089953 21445323 417861 61619...
result:
wrong answer 4th numbers differ - expected: '424628', found: '0'