QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#428084 | #8772. House Deconstruction | ucup-team087# | AC ✓ | 618ms | 88240kb | C++20 | 26.9kb | 2024-06-01 17:21:51 | 2024-06-01 17:21:51 |
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{
(cin >> ... >> a);
}
}
#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]);
#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 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<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<<"}";
}
ll read(){
ll i;
cin>>i;
return i;
}
vi readvi(int n,int off=0){
vi v(n);
rep(i,n)v[i]=read()+off;
return v;
}
pi readpi(int off=0){
int a,b;cin>>a>>b;
return pi(a+off,b+off);
}
template<class t>
void print_single(t x,int suc=1){
cout<<x;
if(suc==1){
if(dbg)cout<<endl;
else cout<<"\n";
}
if(suc==2)
cout<<" ";
}
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?suc:2);
}
template<class T>
void print_offset(const vector<T>&v,ll off,int suc=1){
rep(i,v.size())
print_single(v[i]+off,i==int(v.size())-1?suc:2);
}
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?suc:2);
}
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;
}
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);
}
}
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>
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,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,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 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>;
//mint107 は verify してねえ
//#define DYNAMIC_MOD
struct modinfo{uint mod,root;
#ifdef DYNAMIC_MOD
constexpr modinfo(uint m,uint r):mod(m),root(r),im(0){set_mod(m);}
ull im;
constexpr void set_mod(uint m){
mod=m;
im=ull(-1)/m+1;
}
uint product(uint a,uint b)const{
ull z=ull(a)*b;
uint x=((unsigned __int128)z*im)>>64;
uint v=uint(z)-x*mod;
return v<mod?v:v+mod;
}
#endif
};
template<modinfo const&ref>
struct modular{
static constexpr uint const &mod=ref.mod;
static modular root(){return modular(ref.root);}
uint v;
//modular(initializer_list<uint>ls):v(*ls.bg){}
modular(ll vv=0){s(vv%mod+mod);}
modular& s(uint vv){
v=vv<mod?vv:vv-mod;
return *this;
}
modular operator-()const{return modular()-*this;}
modular& operator+=(const modular&rhs){return s(v+rhs.v);}
modular&operator-=(const modular&rhs){return s(v+mod-rhs.v);}
modular&operator*=(const modular&rhs){
#ifndef DYNAMIC_MOD
v=ull(v)*rhs.v%mod;
#else
v=ref.product(v,rhs.v);
#endif
return *this;
}
modular&operator/=(const modular&rhs){return *this*=rhs.inv();}
modular operator+(const modular&rhs)const{return modular(*this)+=rhs;}
modular operator-(const modular&rhs)const{return modular(*this)-=rhs;}
modular operator*(const modular&rhs)const{return modular(*this)*=rhs;}
modular operator/(const modular&rhs)const{return modular(*this)/=rhs;}
modular pow(ll n)const{
if(n<0)return inv().pow(-n);
modular res(1),x(*this);
while(n){
if(n&1)res*=x;
x*=x;
n>>=1;
}
return res;
}
modular inv()const{return pow(mod-2);}
/*modular inv()const{
int x,y;
int g=extgcd<ll>(v,mod,x,y);
assert(g==1);
if(x<0)x+=mod;
return modular(x);
}*/
friend modular operator+(ll x,const modular&y){
return modular(x)+y;
}
friend modular operator-(ll x,const modular&y){
return modular(x)-y;
}
friend modular operator*(ll x,const modular&y){
return modular(x)*y;
}
friend modular operator/(ll x,const modular&y){
return modular(x)/y;
}
friend ostream& operator<<(ostream&os,const modular&m){
return os<<m.v;
}
friend istream& operator>>(istream&is,modular&m){
ll x;is>>x;
m=modular(x);
return is;
}
bool operator<(const modular&r)const{return v<r.v;}
bool operator==(const modular&r)const{return v==r.v;}
bool operator!=(const modular&r)const{return v!=r.v;}
explicit operator bool()const{
return v;
}
};
#ifndef DYNAMIC_MOD
extern constexpr modinfo base{998244353,3};
//extern constexpr modinfo base{1000000007,0};
//extern constexpr modinfo base{2147483579,1689685080};//2^31 未満の最大の安全素数
//modinfo base{1,0};
#ifdef USE_GOOD_MOD
static_assert(base.mod==998244353);
#endif
#else
modinfo base(1,0);
extern constexpr modinfo base107(1000000007,0);
using mint107=modular<base107>;
#endif
using mint=modular<base>;
mint parity(int i){
return i%2==0?1:-1;
}
#ifdef LOCAL
const int vmax=10010;
#else
const int vmax=(1<<21)+10;
#endif
mint fact[vmax],finv[vmax],invs[vmax];
void initfact(){
const int s=min<int>(vmax,base.mod);
fact[0]=1;
rng(i,1,s){
fact[i]=fact[i-1]*i;
}
finv[s-1]=fact[s-1].inv();
for(int i=s-2;i>=0;i--){
finv[i]=finv[i+1]*(i+1);
}
for(int i=s-1;i>=1;i--){
invs[i]=finv[i]*fact[i-1];
}
}
mint choose(int n,int k){
return inc(0,k,n)?fact[n]*finv[n-k]*finv[k]:0;
}
mint binom(int a,int b){
return 0<=a&&0<=b?fact[a+b]*finv[a]*finv[b]:0;
}
mint catalan(int n){
return binom(n,n)-(n-1>=0?binom(n-1,n+1):0);
}
//対角線を超えず (x,y) に至る方法の数
mint catalan(int x,int y){
assert(y<=x);
return binom(x,y)-binom(x+1,y-1);
}
//y=x+c を超えず (x,y) に至る方法の数
mint catalan(int x,int y,int c){
assert(y<=x+c);
return binom(x,y)-binom(x+c+1,y-c-1);
}
/*
const int vmax=610;
mint fact[vmax+1],binbuf[vmax+1][vmax+1];
mint choose(int n,int k){
return 0<=k&&k<=n?binbuf[n-k][k]:0;
}
mint binom(int a,int b){
return 0<=a&&0<=b?binbuf[a][b]:0;
}
void initfact(int n){
fact[0]=1;
rep(i,n)fact[i+1]=fact[i]*(i+1);
rep(i,n+1)rep(j,n+1){
if(i==0&&j==0){
binbuf[i][j]=1;
}else{
binbuf[i][j]=0;
if(i)binbuf[i][j]+=binbuf[i-1][j];
if(j)binbuf[i][j]+=binbuf[i][j-1];
}
}
}
*/
mint p2[vmax],p2inv[vmax];
void initp2(){
p2[0]=1;
rep(i,vmax-1)p2[i+1]=p2[i]*2;
p2inv[vmax-1]=p2[vmax-1].inv();
per(i,vmax-1)p2inv[i]=p2inv[i+1]*2;
}
int m2i(mint a){
uint v=a.v;
return v<mint::mod/2?v:int(v)-int(mint::mod);
}
//長さ N,要素 0-M-1 のソート列を全探索し,F を呼ぶ
template<class F>
void sorted_array_rec(int n,int m,F f){
vi a(n);
auto rec=[&](auto self,int i)->void{
if(i==n)f(a);
else{
int last=i?a[i-1]:0;
rng(nx,last,m){
a[i]=nx;
self(self,i+1);
}
}
};
rec(rec,0);
}
//vs から k 要素選んだ tuple すべてに対して f を呼ぶ
//ARC177 E
template<class t,class F>
void tuple_rec(const vc<t>&vs,int k,F f){
int n=si(vs);
if(k<=n){
vc<t> a(k);
sorted_array_rec(k,n-k+1,[&](const vi&idx){
rep(i,k)a[i]=vs[idx[i]+i];
f(a);
});
}
};
//極力左と match していると思われる
int mincost_matching_value(vi a,vi b){
assert(is_sorted(all(a)));
assert(is_sorted(all(b)));
int n=si(a),m=si(b);
assert(n<=m);
vi dp(n+m+1,inf);
vi pre(n+m+1,-1);
vi ab(n+m+1);
vi from(n+m+1,-1);
dp[0]=0;
int i=0,j=0;
rep(step,n+m+1){
if(int k=pre[i-j+m];k!=-1){
if(chmin(dp[step],dp[k]+abs(ab[k]-ab[step])))
from[step]=k;
}
pre[i-j+m]=step;
if(step<n+m){
bool useA=true;
if(i==n||(j<m&&a[i]>b[j]))useA=false;
if(useA){
ab[step+1]=ab[step]+a[i];
i++;
}else{
ab[step+1]=ab[step]-b[j];
if(chmin(dp[step+1],dp[step]))
from[step+1]=step;
j++;
}
}
}
return dp.back();
}
//高さが同じところで matching しています
vi mincost_matching_solution(vi a,vi b){
assert(is_sorted(all(a)));
assert(is_sorted(all(b)));
int n=si(a),m=si(b);
assert(n<=m);
vi dp(n+m+1,inf);
vi pre(n+m+1,-1);
vi ab(n+m+1);
vi from(n+m+1,-1);
dp[0]=0;
{
int i=0,j=0;
rep(step,n+m+1){
if(int k=pre[i-j+m];k!=-1){
if(chmin(dp[step],dp[k]+abs(ab[k]-ab[step])))
from[step]=k;
}
pre[i-j+m]=step;
if(step<n+m){
bool useA=true;
if(i==n||(j<m&&a[i]>b[j]))useA=false;
if(useA){
ab[step+1]=ab[step]+a[i];
i++;
}else{
ab[step+1]=ab[step]-b[j];
if(chmin(dp[step+1],dp[step]))
from[step+1]=step;
j++;
}
}
}
}
vi sol(n);
auto match=[&](int i,int j,int len){
static vi is,js;
is.clear();
js.clear();
int iend=i+len,jend=j+len;
rep(step,len*2){
bool useA=true;
if(i==iend||(j<jend&&a[i]>b[j]))useA=false;
if(useA){
is.pb(i++);
}else{
js.pb(j++);
}
if(si(is)&&si(js)){
sol[gpp(is)]=gpp(js);
}
}
assert(i==iend);
assert(j==jend);
};
{
int i=n,j=m;
while(i>0||j>0){
int k=from[i+j];
if(k==i+j-1){
j--;
}else{
int len=i+j-k;
assert(len%2==0);
len/=2;
i-=len;
j-=len;
match(i,j,len);
}
}
}
return sol;
}
//高さが同じところで matching しています
mint mincost_matching_count(vi a,vi b){
assert(is_sorted(all(a)));
assert(is_sorted(all(b)));
int n=si(a),m=si(b);
assert(n<=m);
vi dp(n+m+1,inf);
vi pre(n+m+1,-1);
vi ab(n+m+1);
vi from(n+m+1,-1);
dp[0]=0;
vc<mint> way(n+m+1);
way[0]=1;
auto upd=[&](int s,int t,int add){
if(chmin(dp[t],dp[s]+add)){
from[t]=s;
way[t]=0;
}
if(dp[t]==dp[s]+add)
way[t]+=way[s];
};
{
int i=0,j=0;
rep(step,n+m+1){
if(int k=pre[i-j+m];k!=-1){
//if(chmin(dp[step],dp[k]+abs(ab[k]-ab[step])))
// from[step]=k;
upd(k,step,abs(ab[k]-ab[step]));
}
pre[i-j+m]=step;
if(step<n+m){
bool useA=true;
if(i==n||(j<m&&a[i]>b[j]))useA=false;
if(useA){
ab[step+1]=ab[step]+a[i];
i++;
}else{
ab[step+1]=ab[step]-b[j];
//if(chmin(dp[step+1],dp[step]))
// from[step+1]=step;
upd(step,step+1,0);
j++;
}
}
}
}
return way.back();
}
pair<int,vi> leftist_solution(const int L,const vi&a,const vi&b){
const int n=si(a);
const int m=si(b);
assert(is_sorted(all(a)));
assert(is_sorted(all(b)));
auto c=cat(b-L,b,b+L);
auto getval=[&](int head){
return mincost_matching_value(a,vi(c.bg+head,c.bg+head+m));
};
int lw=0,up=2*m;
while(up-lw>2){
int m1=(lw+lw+up)/3;
int m2=(lw+up+up)/3;
if(getval(m1)<=getval(m2)){
up=m2;
}else{
lw=m1;
}
}
int val=getval(lw),pos=lw;
rng(v,lw+1,up+1)if(chmin(val,getval(v)))pos=v;
vi sol=mincost_matching_solution(a,vi(c.bg+pos,c.bg+pos+m));
rep(i,n)sol[i]=c[sol[i]+pos];
return mp(val,sol);
}
template<class t,class u>
//vc<pi> (val,freq) みたいなやつの val を unique する
void unique_freq(vc<pair<t,u>>&a){
sort(all(a));
int s=0;
rep(i,si(a)){
auto [p,c]=a[i];
if(i==0||a[s-1].a<p){
a[s++]=a[i];
}else{
a[s-1].b+=c;
}
}
a.resize(s);
}
ll fld(ll a, ll b) { // floored division
return a / b - ((a ^ b) < 0 && a % b); }
ll cld(ll a, ll b) { // ceiled division
return a / b + ((a ^ b) > 0 && a % b); }
ll rem(ll a,ll b){
return a-fld(a,b)*b;}
void slv(){
INT(L,n,m);
vi a(n),b(m);
if(dbg){
chmax(m,n+1);
b.resize(m);
L=n+m;
vi idx=vid(n+m);
myshuffle(idx);
rep(i,n)a[i]=gpp(idx);
rep(i,m)b[i]=gpp(idx);
soin(a);
soin(b);
}else{
{
int i=0,j=0;
rep(_,n+m){
INT(p);
STR(t);
p--;
if(t=="P")a[i++]=p;
else if(t=="H")b[j++]=p;
else assert(false);
}
}
}
auto [ansval,es]=leftist_solution(L,a,b);
rein(a);
for(auto&v:a)v=L-1-v;
rein(b);
for(auto&v:b)v=L-1-v;
auto [anstmp,fs]=leftist_solution(L,a,b);
rein(a);
for(auto&v:a)v=L-1-v;
rein(b);
for(auto&v:b)v=L-1-v;
assert(ansval==anstmp);
rein(fs);
for(auto&i:fs)i=L-1-i;
dmp(es);
dmp(fs);
vc<pi> qs;
/*rep(i,n){
qs.eb(a[i],-1);
qs.eb(rem(es[i],L),+1);
}
rep(i,n){
qs.eb(a[i],1);
qs.eb(rem(fs[i],L),-1);
}*/
auto add=[&](int l,int r){
if(l>r)swap(l,r);
qs.eb(rem(l,L),1);
qs.eb(rem(r,L),-1);
};
rep(i,n){
add(a[i],es[i]);
}
rep(i,n){
add(a[i],fs[i]);
}
mint answay=1;
{
unique_freq(qs);
int s=si(qs);
vi sum(s+1);
rep(i,s)sum[i+1]=sum[i]+qs[i].b;
//sum-=MIN(sum);
//assert(MAX(sum)<=1);
int pos=qs[MINi(sum).b].a;
vi c=a-pos,d=b-pos;
for(auto&v:c)if(v<0)v+=L;
for(auto&v:d)if(v<0)v+=L;
soin(c);
soin(d);
answay=mincost_matching_count(c,d);
}
if(dbg){
/*
int godval=inf,godway=0;
tuple_rec(b,n,[&](vi c){
auto [cur,sol]=leftist_solution(L,a,c);
if(chmin(godval,cur))godway=0;
if(godval==cur)godway++;
});
if(godval!=ansval||godway!=answay){
cerr<<a<<endl;
cerr<<b<<endl;
cerr<<godval<<" "<<godway<<endl;
cerr<<ansval<<" "<<answay<<endl;
vc<pair<int,char>> ls;
rep(i,n)ls.eb(a[i]+1,'P');
rep(i,m)ls.eb(b[i]+1,'H');
soin(ls);
print(L,n,m);
for(auto [v,c]:ls)print(v,c);
cout.flush();
assert(false);
}*/
}else{
print(ansval);
print(answay);
}
}
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;cin>>t;rep(_,t)
slv();
}
}
详细
Test #1:
score: 100
Accepted
time: 11ms
memory: 44608kb
input:
6 2 4 1 P 2 H 3 P 4 H 5 H 6 H
output:
2 3
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 7ms
memory: 44616kb
input:
1000000000 2 4 1 P 6 H 31415926 H 999999998 H 999999999 H 1000000000 P
output:
4 1
result:
ok 2 lines
Test #3:
score: 0
Accepted
time: 618ms
memory: 86248kb
input:
1000000000 199999 200000 3087 P 3282 H 6407 H 6748 P 9535 P 10098 H 16470 H 22311 H 31045 H 31968 H 32549 H 33037 P 36005 P 36308 H 40284 P 46224 H 52394 P 54922 H 55800 P 56582 H 57548 H 62155 P 63067 P 64237 H 66133 P 71351 P 75667 P 79089 P 79646 P 81144 H 91883 P 96680 H 102797 H 105388 H 105971...
output:
262753966206 1
result:
ok 2 lines
Test #4:
score: 0
Accepted
time: 583ms
memory: 84180kb
input:
1000000000 150000 200000 3087 P 3282 H 6407 H 6748 H 9535 H 10098 H 16470 H 22311 H 31968 H 32549 H 33037 P 36005 P 40284 H 52394 P 54922 H 55800 H 56582 H 57548 H 62155 P 63067 P 64237 H 66133 P 71351 P 75667 H 79089 P 79646 P 81144 H 91883 P 96680 H 102797 H 105388 H 105971 P 106057 P 107807 P 116...
output:
1212175277 8
result:
ok 2 lines
Test #5:
score: 0
Accepted
time: 263ms
memory: 72468kb
input:
1000000000 100000 200000 3068 H 3087 P 3106 H 33031 H 33037 P 33043 H 52370 H 52394 P 52418 H 62996 H 63067 P 63138 H 66040 H 66133 P 66226 H 71350 H 71351 P 71352 H 91852 H 91883 P 91914 H 105924 H 105969 H 105971 P 106018 H 106057 P 106145 H 116361 H 116385 P 116409 H 126036 H 126084 P 126132 H 12...
output:
4978306 463697368
result:
ok 2 lines
Test #6:
score: 0
Accepted
time: 590ms
memory: 84112kb
input:
1000000 150000 200000 2 H 3 H 6 H 8 H 16 P 17 H 19 P 20 P 21 P 24 H 28 H 33 H 37 P 38 H 40 H 44 P 48 H 49 P 58 P 59 P 60 H 62 P 65 P 70 H 72 H 76 P 77 H 79 P 84 P 93 H 96 P 101 H 104 H 106 P 110 H 111 P 112 H 116 H 124 P 125 H 126 H 127 H 128 P 134 H 135 P 137 P 138 P 140 H 142 H 145 H 146 H 147 H 1...
output:
1203722 86861366
result:
ok 2 lines
Test #7:
score: 0
Accepted
time: 380ms
memory: 88240kb
input:
1000000000 199999 200000 966788248 H 966788251 P 966788252 H 966788254 P 966788255 H 966788260 P 966788261 H 966788263 P 966788267 H 966788275 P 966788278 H 966788279 P 966788288 H 966788291 P 966788298 H 966788304 P 966788305 H 966788308 P 966788309 H 966788317 P 966788326 H 966788334 P 966788342 H...
output:
1098446 4586
result:
ok 2 lines
Test #8:
score: 0
Accepted
time: 231ms
memory: 80668kb
input:
10000000 137967 139896 52 P 101 H 106 P 149 P 158 P 190 P 258 P 338 P 349 P 350 P 457 P 486 P 500 P 509 P 517 P 563 P 568 P 630 P 723 P 738 P 801 P 819 P 859 P 872 P 885 P 900 P 972 P 1004 P 1034 P 1087 P 1183 P 1236 P 1245 P 1268 P 1436 H 1481 P 1486 P 1511 P 1544 P 1607 P 1647 P 1685 P 1798 P 1819...
output:
317845182248 2
result:
ok 2 lines
Test #9:
score: 0
Accepted
time: 249ms
memory: 80508kb
input:
400000 137967 139896 1 P 2 H 3 P 4 P 5 P 6 P 9 P 10 P 11 P 15 P 16 P 17 P 18 P 19 P 20 P 22 P 23 P 24 P 26 P 27 P 28 P 29 P 31 P 32 P 33 P 34 P 35 P 36 P 37 P 39 P 40 P 45 P 47 P 48 P 49 H 51 P 52 P 53 P 56 P 57 P 58 P 60 P 61 P 62 P 63 P 64 P 65 P 68 P 71 P 72 P 73 P 74 H 75 P 76 P 77 P 78 P 79 P 8...
output:
12717669314 562027925
result:
ok 2 lines
Test #10:
score: 0
Accepted
time: 396ms
memory: 86976kb
input:
1000000000 199000 200000 526190 H 526213 P 526214 H 526299 P 526309 H 526316 P 526351 H 526355 P 526370 H 526400 P 526482 H 526545 P 526569 H 526573 P 526641 H 526658 P 526707 H 526790 P 526838 H 526844 P 526868 H 526967 P 526975 H 527032 P 527097 H 527154 P 527213 H 527278 P 527299 H 527367 P 52743...
output:
9896423 922405585
result:
ok 2 lines
Test #11:
score: 0
Accepted
time: 400ms
memory: 88060kb
input:
1000000000 199950 200000 5239074 H 5239076 P 5239077 H 5239078 P 5239079 H 5239080 P 5239081 H 5239083 P 5239084 H 5239085 P 5239086 H 5239087 P 5239088 H 5239090 P 5239092 H 5239093 P 5239094 H 5239095 P 5239097 H 5239099 P 5239101 H 5239102 P 5239103 H 5239104 P 5239105 H 5239106 P 5239107 H 52391...
output:
299836 463541155
result:
ok 2 lines
Test #12:
score: 0
Accepted
time: 438ms
memory: 87944kb
input:
1000000000 199500 200000 244421 H 244423 P 244424 H 244425 P 244426 H 244427 P 244428 H 244430 P 244431 H 244432 P 244433 H 244434 P 244435 H 244437 P 244439 H 244440 P 244441 H 244442 P 244444 H 244446 P 244448 H 244449 P 244450 H 244451 P 244452 H 244453 P 244454 H 244455 P 244456 H 244458 P 24446...
output:
298242 524810405
result:
ok 2 lines
Test #13:
score: 0
Accepted
time: 244ms
memory: 82536kb
input:
400000 148599 151281 2 P 3 P 5 P 6 P 7 P 8 P 9 P 10 P 11 P 12 P 13 P 14 P 15 P 16 P 17 P 18 P 19 P 22 P 23 P 25 P 30 P 31 P 32 P 33 H 34 P 35 P 36 P 38 P 39 P 40 P 41 P 43 P 45 P 47 P 49 P 50 P 51 P 53 P 54 P 55 P 57 P 58 P 60 H 61 P 62 H 65 P 67 P 68 P 69 P 70 P 71 P 72 P 73 P 74 P 77 P 78 P 79 P 8...
output:
13764808569 268118240
result:
ok 2 lines
Test #14:
score: 0
Accepted
time: 511ms
memory: 82408kb
input:
1000000000 149183 174434 2 H 6 P 10 H 12 H 13 H 14 H 18 P 21 P 23 H 24 H 25 H 30 H 32 H 35 H 37 P 39 P 41 H 53 P 57 H 61 P 62 P 63 P 65 H 66 P 67 H 71 P 73 H 74 P 75 P 76 H 78 H 79 H 80 H 82 P 83 P 84 H 85 H 93 H 95 H 96 P 99 H 107 P 108 P 109 P 111 H 112 P 116 H 118 P 119 H 120 P 121 P 123 H 124 P ...
output:
1788748 930867409
result:
ok 2 lines