QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#223762 | #6633. Exam Requirements | jby | RE | 7ms | 87488kb | C++20 | 3.7kb | 2023-10-22 16:42:45 | 2023-10-22 16:42:46 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define db double
#define pint pair<int,int>
#define mk make_pair
#define pb push_back
#define eb emplace_back
#define ins insert
#define fi first
#define se second
#define For(x, y, z) for(int x = (y); x <= (z); x++)
#define Rep(x, y, z) for(int x = (y); x >= (z); x--)
using namespace std;
const int MAXN = 1e5 + 5;
char buf[1 << 12], *pp1 = buf, *pp2 = buf, nc;
inline char gc() {
return (pp1 == pp2) && (pp2 = (pp1 = buf) + fread(buf, 1, 1 << 12, stdin), pp1 == pp2) ? EOF : *pp1++;
}
inline int read() {
int x = 0, ny = 1;
for(; nc = gc(), (nc < 48 || nc > 57) && nc != EOF; )
if(nc == '-') ny = -1;
if(nc < 0) return nc;
x = nc ^ 48;
for(; nc = gc(), (nc >= 48 && nc <= 57 && nc != EOF); )
x = (x << 3) + (x << 1) + (nc ^ 48);
return x * ny;
}
int n, m, p[MAXN << 1], rt[MAXN], id[MAXN], cnt, tot = 0;
pint seg[MAXN];
vector<int> G[MAXN * 30];
int dfn[MAXN * 30], low[MAXN * 30], vis[MAXN * 30], stk[MAXN * 30], top, bel[MAXN * 30], N;
void dfs(int x) {
dfn[x] = low[x] = ++dfn[0], vis[x] = 1, stk[++top] = x;
for(auto y : G[x]) {
if(!dfn[y]) {
dfs(y), low[x] = min(low[x], low[y]);
} else if(vis[y]) low[x] = min(low[x], dfn[y]);
}
if(dfn[x] == low[x]) {
++N;
for(int u = 0; u != x; ) u = stk[top--], vis[u] = 0, bel[u] = N;
}
}
inline void addEdge(int x, int y) {
if(!x || !y) return ;
// cout << x << ' ' << y << '\n';
G[x].push_back(y);
}
int ls[MAXN * 30], rs[MAXN * 30];
inline void addEdge(int x, int l, int r, int ql, int qr, int s) {
if(!x) return ;
if(ql <= l && r <= qr) {
addEdge(s, x);
return ;
}
int mid = l + r >> 1;
if(qr <= mid) addEdge(ls[x], l, mid, ql, qr, s);
else if(ql > mid) addEdge(rs[x], mid + 1, r, ql, qr, s);
else addEdge(ls[x], l, mid, ql, qr, s), addEdge(rs[x], mid + 1, r, ql, qr, s);
}
inline void ins(int &x, int l, int r, int pos, int t) {
int tt = x;
x = ++tot, ls[x] = rs[tt], rs[x] = ls[tt], G[x].clear(), addEdge(x, tt);
if(l == r) {
addEdge(x, t);
return ;
}
int mid = l + r >> 1;
if(pos <= mid) {
ins(ls[x], l, mid, pos, t);
addEdge(x, ls[x]);
} else {
ins(rs[x], mid + 1, r, pos, t);
addEdge(x, rs[x]);
}
}
inline void Solve() {
n = read(), m = read();
For(i, 1, n) {
p[++cnt] = seg[i].fi = read();
p[++cnt] = seg[i].se = read();
}
sort(p + 1, p + cnt + 1), cnt = unique(p + 1, p + cnt + 1) - p - 1;
For(i, 1, n) {
id[i] = i;
seg[i].fi = lower_bound(p + 1, p + cnt + 1, seg[i].fi) - p;
seg[i].se = lower_bound(p + 1, p + cnt + 1, seg[i].se) - p;
}
sort(id + 1, id + n + 1, [] (int a, int b) {return seg[a] <= seg[b];});
For(i, 1, 2 * n) G[i].clear();
tot = 2 * n, rt[0] = 0;
For(i, 1, n) {
addEdge(rt[i - 1], 1, cnt, seg[i].fi, cnt, id[i]);
rt[i] = rt[i - 1], ins(rt[i], 1, cnt, seg[i].se, id[i] + n);
}
rt[n + 1] = 0;
Rep(i, n, 1) {
addEdge(rt[i + 1], 1, cnt, 1, seg[i].se, id[i]);
rt[i] = rt[i + 1], ins(rt[i], 1, cnt, seg[i].fi, id[i] + n);
}
For(i, 1, m) {
int a = read(), b = read();
addEdge(a + n, b), addEdge(b + n, a);
}
For(i, 1, tot) dfn[i] = low[i] = vis[i] = 0;
top = dfn[0] = 0, N = 0;
For(i, 1, tot) if(!dfn[i]) dfs(i);
For(i, 1, n) if(bel[i] == bel[i + n]) {
puts("NO");
return;
}
puts("YES");
}
int main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
for(int t = read(); t--; )
Solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 7ms
memory: 87488kb
input:
2 3 1 1 5 2 7 10 11 2 1 3 3 1 5 2 7 5 7 1 2 2 3 3 1
output:
YES NO
result:
ok 2 lines
Test #2:
score: -100
Runtime Error
input:
1 100000 100000 15084647 15220430 217541056 217598054 222963701 223110976 71224450 71340221 320463268 320631387 334861459 334924668 328950591 329083669 178996498 178996584 428529461 428605033 405428435 405504132 197936687 197947412 9058562 9190197 169407597 169474101 297518153 297590927 31471874 316...