結果

問題 No.1914 Directed by Two Sequences
ユーザー lgswdn
提出日時 2025-04-18 14:11:44
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 538 ms / 3,000 ms
コード長 4,772 bytes
コンパイル時間 2,912 ms
コンパイル使用メモリ 218,876 KB
実行使用メモリ 105,108 KB
最終ジャッジ日時 2025-04-18 14:12:14
合計ジャッジ時間 27,236 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

//Shirasu Azusa 2025.4
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef double ld;
typedef long long ll;
typedef unsigned long long ull;
template<typename T,typename U>
T ceil(T x, U y) {return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>
T floor(T x, U y) {return (x>0?x/y:(x-y+1)/y);}
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x)  {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x)  {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x)  {return (x==0?-1:__builtin_ctzll(x));}

#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;
int read() {
  int x=0,w=1; char c=getchar(); 
  while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
  while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();} 
  return x*w;
}

const int N=4e5+5;
int n,m,a[N],b[N],vst[N],deg[N],cur[N]; stack<int> st;
vi be[N],ce[N]; map<pii,int> bpm;
vp e[N],bed;
int tot,id[N]; vi p[N];

#define ls (p<<1)
#define rs (p<<1|1)
pii mina[N],maxb[N],maxa[N],minb[N];
void psu(int p) {
  mina[p]=min(mina[ls],mina[rs]);
  maxa[p]=max(maxa[ls],maxa[rs]);
  maxb[p]=max(maxb[ls],maxb[rs]);
  minb[p]=min(minb[ls],minb[rs]);
}
void build(int p,int l,int r) {
  if(l==r) {mina[p]=maxa[p]=pii(a[l],l), maxb[p]=minb[p]=pii(b[l],l); return;}
  int mid=l+r>>1; build(ls,l,mid), build(rs,mid+1,r); psu(p);
}
void del(int p,int l,int r,int x) {
  if(l==r) {mina[p]=minb[p]=pii(4*N,l), maxb[p]=maxa[p]=pii(-1,l); return;}
  int mid=l+r>>1; if(x<=mid) del(ls,l,mid,x); else del(rs,mid+1,r,x); psu(p);
}
pii qmin(pii *mina,int p,int l,int r,int x,int y) {
  if(l==x&&r==y) return mina[p]; int mid=l+r>>1;
  if(y<=mid) return qmin(mina,ls,l,mid,x,y);
  else if(x>mid) return qmin(mina,rs,mid+1,r,x,y);
  else return min(qmin(mina,ls,l,mid,x,mid),qmin(mina,rs,mid+1,r,mid+1,y));;
}
pii qmax(pii *maxb,int p,int l,int r,int x,int y) {
  if(l==x&&r==y) return maxb[p]; int mid=l+r>>1;
  if(y<=mid) return qmax(maxb,ls,l,mid,x,y);
  else if(x>mid) return qmax(maxb,rs,mid+1,r,x,y);
  else return max(qmax(maxb,ls,l,mid,x,mid),qmax(maxb,rs,mid+1,r,mid+1,y));;
}

void dfs1(int u) {
  vst[u]=1; del(1,1,n,u);
  for(auto [l,r]:e[u]) {
    for(;u<l;) {
      auto [bv,v]=qmax(maxb,1,1,n,l,r);
      if(a[u]<bv) dfs1(v); else break;
    }
    for(;u>r;) {
      auto [av,v]=qmax(maxa,1,1,n,l,r);
      if(b[u]<av) dfs1(v); else break;
    }
  } st.push(u);
}
void dfs2(int u) {
  vst[u]=1; del(1,1,n,u); id[u]=tot; p[tot].eb(u);
  for(auto [l,r]:e[u]) {
    for(;u<l;) {
      auto [bv,v]=qmin(minb,1,1,n,l,r);
      if(a[u]>bv) dfs2(v); else break;
    }
    for(;u>r;) {
      auto [av,v]=qmin(mina,1,1,n,l,r);
      if(b[u]>av) dfs2(v); else break;
    }
  }
}

bool qed(int u,int v) {
  if(u>v) swap(u,v);
  int toted=p[u].size()*p[v].size();
  return toted-bpm[pii(u,v)]>0;
}

signed main() {
  n=read(), m=read();
  rep(i,1,n) a[i]=read();
  rep(i,1,n) b[i]=read();
  rep(i,1,n) be[i].eb(i), be[i].eb(n+1);
  map<pii,int> tttmp;
  rep(i,1,m) {
    int u=read(), v=read();
    be[u].eb(v), be[v].eb(u);
    bed.eb(u,v);
    tttmp[pii(u,v)]=tttmp[pii(v,u)]=1;
  }
  rep(i,1,n) {
    int lst=0;
    sort(be[i].begin(),be[i].end());
    for(int x:be[i]) {if(lst+1<x) e[i].eb(lst+1,x-1); lst=x;}
  }
  build(1,1,n);
  rep(i,1,n) if(!vst[i]) dfs1(i);
  rep(i,1,n) vst[i]=0;
  build(1,1,n);
  while(!st.empty()) {int x=st.top(); if(!vst[x]) ++tot, dfs2(x); st.pop();} 
  rep(i,1,n) vst[i]=0;
  for(auto [u,v]:bed) {
    int x=id[u], y=id[v]; if(x>y) swap(x,y);
    bpm[pii(x,y)]++;
  }
  vi tmp,rmp; tmp.eb(tot);
  per(i,tot-1,1) {
    queue<int> q;
    for(int x:tmp) if(deg[x]==0) q.push(x); tmp.clear();
    while(!q.empty()) {
      int u=q.front(); q.pop(); tmp.eb(u);
      if(qed(i,u)) ce[i].eb(u), deg[u]++;
      else {
        for(int x:ce[u]) {
          cur[x]--; rmp.eb(x);
          if(!cur[x]) q.push(x);
        }
      }
    }
    for(int x:tmp) cur[x]=deg[x];
    for(int x:rmp) cur[x]=deg[x];
    tmp.eb(i); rmp.clear();
  }
  int ans=0;
  rep(i,1,tot) if(p[i].size()>1) ans+=p[i].size();
  rep(i,1,tot) ans+=ce[i].size();
  printf("%d\n",ans);
  rep(i,1,tot) if(p[i].size()>1) {
    int m=p[i].size();
    rep(j,0,m-1) printf("%d %d\n",p[i][j],p[i][(j+1)%m]);
  }
  int ccc=0;
  rep(i,1,tot) for(int j:ce[i]) printf("%d %d\n",p[i][0],p[j][0]), ccc++;
  //assert(ccc==tot-1);
  return 0;
}
0