QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#485327 | #6632. Minimize Median | ucup-team1525# | RE | 0ms | 0kb | C++20 | 2.0kb | 2024-07-20 16:28:20 | 2024-07-20 16:28:20 |
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e5,T=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);
}
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));
}
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(); e[i].shrink_to_fit();
}
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 work(){
}
}S;
void solve(){
scanf("%d %d",&n,&m);
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;
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;
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;
}
詳細信息
Test #1:
score: 0
Runtime Error
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