QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#485355 | #6632. Minimize Median | ucup-team1525# | WA | 6ms | 44500kb | C++20 | 3.1kb | 2024-07-20 16:49:44 | 2024-07-20 16:49:45 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e5,T=1.1e6;
int n,m;
struct Int{
int l,r;
Int(int l=0,int r=0):l(l),r(r){}
}a[N+5];
int xs,x[N+5];
struct Re{
int x,y;
Re(int x=0,int y=0):x(x),y(y){}
}b[N+5];
struct SAT2{
int tot;
vector<int> e[T+5];
int tr[T+5];
#define lc id<<1
#define rc id<<1|1
void adde(int u,int v){
e[u].push_back(v);
// printf("%d %d\n",u,v);
}
void addex(int u,int cu,int v,int cv){
e[u<<1|cu].push_back(v<<1|cv);
e[v<<1|(cv^1)].push_back(u<<1|(cu^1));
// printf("%d %d\n",u<<1|cu,v<<1|cv);
// printf("%d %d\n",v<<1|(cv^1),u<<1|(cu^1));
}
void build(int l,int r,int id){
tr[id]=++tot;
if(l==r){
adde(tr[id]<<1|1,tr[id]<<1);
return;
}
int mid=l+r>>1;
build(l,mid,lc);
build(mid+1,r,rc);
addex(tr[id],1,tr[lc],1);
addex(tr[id],1,tr[rc],1);
}
void init(int n){
for(int i=1;i<=tot;i++)
e[i].clear();
tot=n;
build(1,xs,1);
}
void cover(int l,int r,int st,int en,int u,int id){
if(st<=l&&en>=r){
addex(u,1,tr[id],1);
return;
}
int mid=l+r>>1;
if(st<=mid) cover(l,mid,st,en,u,lc);
if(en>mid) cover(mid+1,r,st,en,u,rc);
}
bool vis[T+5],in[T+5];
int st[T+5],ss;
int dfn[T+5],low[T+5],dfns;
int bl[T+5],cnt;
void dfs(int u){
vis[u]=1;
dfn[u]=low[u]=++dfns;
in[u]=1; st[++ss]=u;
for(auto v:e[u]){
if(!vis[v]){
dfs(v);
low[u]=min(low[u],low[v]);
}
else if(in[v]) low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u]){
cnt++;
while(st[ss]!=u){
bl[st[ss]]=cnt;
in[st[ss]]=0;
ss--;
}
bl[u]=cnt; in[u]=0; ss--;
}
}
bool work(){
ss=0; dfns=0; cnt=0;
for(int i=2;i<=tot*2+1;i++){
vis[i]=in[i]=dfn[i]=low[i]=bl[i]=0;
}
for(int i=2;i<=tot*2+1;i++)
if(!vis[i]) dfs(i);
for(int i=1;i<=tot;i++)
if(bl[i<<1|1]==bl[i<<1]) return 0;
return 1;
}
}S;
void solve(){
scanf("%d %d",&n,&m);
xs=0;
for(int i=1;i<=n;i++){
scanf("%d %d",&a[i].l,&a[i].r);
x[++xs]=a[i].l; x[++xs]=a[i].r+1;
}
for(int i=1;i<=m;i++)
scanf("%d %d",&b[i].x,&b[i].y);
sort(x+1,x+1+xs);
xs=unique(x+1,x+1+xs)-x-1;
// for(int i=1;i<=xs;i++)
// printf("%d ",x[i]);
// puts("");
S.init(n);
for(int i=1;i<=n;i++){
a[i].l=lower_bound(x+1,x+1+xs,a[i].l)-x;
a[i].r=lower_bound(x+1,x+1+xs,a[i].r+1)-x-1;
// printf("%d %d\n",a[i].l,a[i].r);
S.cover(1,xs,a[i].l,a[i].r,i,1);
}
for(int i=1;i<=m;i++)
S.addex(b[i].x,0,b[i].y,1);
puts(S.work()?"YES":"NO");
}
int main(){
int t; scanf("%d",&t);
while(t--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 6ms
memory: 44500kb
input:
3 3 5 0 2 5 2 3 2 4 6 13 3 5 3 2 5 3 3 2 4 6 13 3 5 6 2 5 2 3 2 4 6 13
output:
NO NO NO
result:
wrong output format Expected integer, but "NO" found