QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #567545 | #9310. Permutation Counting 4 | Violet2726 | WA | 1077ms | 98376kb | Java11 | 12.6kb | 2024-09-16 12:38:56 | 2024-09-16 12:38:56 |
Judging History
answer
import java.io.*;
import java.util.*;
public class Main {
static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
static Reader in = new Reader();
static int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
static int[][] dirs_8 = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
static long LNF = Long.MAX_VALUE / 2;
static int INF = Integer.MAX_VALUE / 2;
static long BASE = 131;
public static void main(String[] args) {
int t = in.nextInt();
// int t = 1;
while (t-- > 0) {
solve();
}
out.close();
}
static long MOD = (long) 998244353;
static int N = (int) 1e6 + 10, M = (int) 2e5 + 10;
static void solve() {
int n = in.nextInt();
int[][] grid = in.nextIntArray2(n, 2);
Arrays.sort(grid, (a, b) -> a[1] - b[1]);
Map<Integer, Set<Integer>> left = new HashMap<>();
for (int i = 0; i < n; i++) {
int l = grid[i][0], r = grid[i][1];
left.computeIfAbsent(r, e -> new HashSet<>());
if (left.get(r).contains(l)) {
out.println(0);
return;
}
Set<Integer> x = left.getOrDefault(l - 1, new HashSet<>()), y = left.get(r);
int size = x.size() + y.size();
y.addAll(x);
if (y.size() != size) {
out.println(0);
return;
}
y.add(l);
}
out.println(1);
}
static class SplayTree {
static class Node {
int[] son = new int[2];
int pa, val, cnt, size;
void init(int pa, int val) {
this.pa = pa;
this.val = val;
this.cnt = this.size = 1;
}
}
int N = (int) 1100000;
Node[] st = new Node[N];
int root = 0, idx = 0;
SplayTree() {
Arrays.setAll(st, e -> new SplayTree.Node());
}
void pushUp(int x) {
st[x].size = st[ls(x)].size + st[rs(x)].size + st[x].cnt;
}
int ls(int x) {
return st[x].son[0];
}
int rs(int x) {
return st[x].son[1];
}
void rotate(int x) { // 旋转
int y = st[x].pa, z = st[y].pa;
st[z].son[st[z].son[0] == y ? 0 : 1] = x;
st[x].pa = z;
int k = st[y].son[0] == x ? 0 : 1;
int t = st[x].son[k ^ 1];
st[y].son[k] = t;
st[t].pa = y;
st[x].son[k ^ 1] = y;
st[y].pa = x;
pushUp(y);
pushUp(x);
}
// k == 0 ：把 x 转为根
// k ！= 0 ：把 x 转到 k 下面
void splay(int x, int k) {
while (st[x].pa != k) {
int y = st[x].pa, z = st[y].pa;
if (z != k) {
if ((ls(y) == x) ^ (ls(z) == y)) {
rotate(x);
} else {
rotate(y);
}
}
rotate(x);
}
if (k == 0) {
root = x;
}
}
void insert(int val) {
int x = root, p = 0;
while (x != 0 && st[x].val != val) {
p = x;
x = st[x].son[val < st[x].val ? 0 : 1];
}
if (x != 0) {
st[x].cnt++;
} else {
x = ++idx;
if (p != 0) {
st[p].son[val < st[p].val ? 0 : 1] = x;
}
st[x].init(p, val);
}
splay(x, 0);
}
void find(int val) { // 找到值为 val 的节点，同时将其转为根
int x = root;
while (st[x].son[val < st[x].val ? 0 : 1] != 0 && val != st[x].val) {
x = st[x].son[val < st[x].val ? 0 : 1];
}
splay(x, 0);
}
int getPre(int val) { // 前驱的节点编号
find(val);
int x = root;
if (st[x].val < val) {
return x;
}
x = ls(x);
while (rs(x) != 0) {
x = rs(x);
}
splay(x, 0);
return x;
}
int getPreVal(int val) {
return st[getPre(val)].val;
}
int getSuf(int val) { // 后继的节点编号
find(val);
int x = root;
if (st[x].val > val) {
return x;
}
x = rs(x);
while (ls(x) != 0) {
x = ls(x);
}
splay(x, 0);
return x;
}
int getSufVal(int val) {
return st[getSuf(val)].val;
}
void del(int val) {
int pre = getPre(val), suf = getSuf(val);
splay(pre, 0);
splay(suf, pre);
int del = st[suf].son[0];
if (st[del].cnt > 1) {
st[del].cnt--;
splay(del, 0);
} else {
st[suf].son[0] = 0;
splay(suf, 0);
}
}
int getValOfRank(int rank) { // 获取排名为 rank 的值
rank++; // 注意哨兵的存在
int x = root;
while (true) {
if (rank <= st[ls(x)].size) {
x = ls(x);
} else if (rank <= st[ls(x)].size + st[x].cnt) {
break;
} else {
rank -= st[ls(x)].size + st[x].cnt;
x = rs(x);
}
}
splay(x, 0);
return st[x].val;
}
int getRankOfVal(int val) { // 获取值的排名
insert(val);
int rank = st[ls(root)].size;
del(val);
return rank;
}
}
static void setOut(String path) {
try {
out = new PrintWriter(new FileOutputStream(path));
} catch (FileNotFoundException e) {
throw new RuntimeException(e);
}
}
static long lowbit(long x) {
return x & -x;
}
static void swap(char[] s, int i, int j) {
char t = s[i];
s[i] = s[j];
s[j] = t;
}
static <T> void swap(T[] nums, int i, int j) {
T t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
static long pow(long x, long n) {
if (n <= 0) {
return 1;
}
long res = 1;
for (; n > 0; n >>= 1, x = x * x) {
if ((n & 1) == 1) {
res = res * x;
}
}
return res;
}
static long pow(long x, long n, long mod) {
if (n <= 0) {
return 1;
}
x %= mod;
long res = 1;
for (; n > 0; n >>= 1, x = x * x % mod) {
if ((n & 1) == 1) {
res = res * x % mod;
}
}
return res;
}
static long gcd(long a, long b) {
return b == 0 ? a : gcd(b, a % b);
}
static int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
static int getBit(int s, int i) {
return (s >> i) & 1;
}
static int getBit(long s, int i) {
return (int) (s >> i) & 1;
}
static int setBit(int s, int i, int b) {
if (getBit(s, i) == 1) s ^= 1 << i;
return s | b << i;
}
static long max(long... nums) {
long res = -LNF;
for (long x : nums) {
res = Math.max(res, x);
}
return res;
}
static int max(int... nums) {
int res = -INF;
for (int x : nums) {
res = Math.max(res, x);
}
return res;
}
static long min(long... nums) {
long res = LNF;
for (long x : nums) {
res = Math.min(res, x);
}
return res;
}
static int min(int... nums) {
int res = INF;
for (int x : nums) {
res = Math.min(res, x);
}
return res;
}
static List<Integer>[] build_graph(int n, int m) {
List<Integer>[] g = new List[n + 1];
Arrays.setAll(g, e -> new ArrayList<>());
for (int i = 0; i < m; i++) {
int x = in.nextInt(), y = in.nextInt();
g[x].add(y);
g[y].add(x);
}
return g;
}
static <T> void print(List<T> list) {
for (T x : list) {
out.print(x + " ");
}
out.println();
}
static class UnionFind {
int[] parent;
int size;
int[] counts;
UnionFind(int n) {
size = n;
parent = new int[n];
Arrays.setAll(parent, i -> i);
counts = new int[n];
Arrays.fill(counts, 1);
}
int find(int x) {
while (parent[x] != x) {
x = parent[x] = parent[parent[x]];
}
return x;
}
boolean union(int x, int y) {
x = find(parent[x]);
y = find(parent[y]);
if (x == y) {
return false;
}
parent[x] = y;
counts[y] += counts[x];
size--;
return true;
}
int getSize() {
return size;
}
int getCount(int x) {
return counts[find(x)];
}
boolean connect(int x, int y) {
return find(parent[x]) == find(parent[y]);
}
void set(int x, int fa) {
parent[x] = fa;
}
}
static class Reader {
private BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private StringTokenizer st;
void set(String path) {
try {
br = new BufferedReader(new FileReader(path));
} catch (Exception ignored) {
}
}
boolean hasNext() {
try {
while (st == null || !st.hasMoreElements()) {
st = new StringTokenizer(br.readLine());
}
} catch (Exception e) {
return false;
}
return true;
}
String next() {
try {
while (st == null || !st.hasMoreElements()) {
st = new StringTokenizer(br.readLine());
}
} catch (Exception ignored) {
}
return st.nextToken();
}
String nextLine() {
String s = "";
try {
s = br.readLine();
} catch (Exception ignored) {
}
return s;
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return java.lang.Long.parseLong(next());
}
int[] nextIntArray(int n, int start) {
int[] arr = new int[n + start];
for (int i = start; i < arr.length; i++) {
arr[i] = nextInt();
}
return arr;
}
int[] nextIntArray(int n) {
return nextIntArray(n, 0);
}
int[][] nextIntArray2(int n, int m) {
int[][] grid = new int[n][];
Arrays.setAll(grid, i -> grid[i] = nextIntArray(m));
return grid;
}
long[] nextLongArray(int n, int start) {
long[] arr = new long[n + start];
for (int i = start; i < arr.length; i++) {
arr[i] = nextLong();
}
return arr;
}
long[] nextLongArray(int n) {
return nextLongArray(n, 0);
}
long[][] nextLongArray2(int n, int m) {
long[][] grid = new long[n][];
Arrays.setAll(grid, i -> grid[i] = nextLongArray(m));
return grid;
}
char[][] nextCharArray(int n) {
char[][] grid = new char[n][];
Arrays.setAll(grid, i -> grid[i] = nextLine().toCharArray());
return grid;
}
String[] nextStrArray(int n) {
String[] arr = new String[n];
Arrays.setAll(arr, i -> arr[i] = nextLine());
return arr;
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 58ms
memory: 51628kb
input:
4 5 1 2 1 5 1 2 1 2 2 2 5 1 1 2 4 2 3 5 5 3 4 5 3 5 1 2 3 4 3 5 3 3 5 1 5 1 4 4 5 5 5 1 2
output:
0 1 0 0
result:
ok 4 tokens
Test #2:
score: -100
Wrong Answer
time: 1077ms
memory: 98376kb
input:
66725 14 7 7 4 6 7 8 8 13 2 13 6 13 6 10 14 14 1 10 9 11 7 9 3 8 4 12 5 12 12 2 6 3 6 7 11 2 5 1 1 6 12 8 12 2 3 7 9 7 8 1 10 1 4 10 4 8 4 4 6 10 9 10 2 3 2 7 1 3 3 4 2 2 3 10 20 3 12 10 14 19 20 19 20 1 9 7 9 13 16 17 17 16 18 2 11 5 19 6 17 11 17 3 6 3 11 7 20 8 17 3 18 10 15 9 20 16 5 10 2 10 2 1...
output:
1 1 0 0 1 0 1 1 0 1 1 0 0 0 0 0 1 0 1 0 0 1 0 0 1 1 0 1 0 0 0 1 1 0 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 0 1 1 1 0 1 0 1 0 1 0 1 1 0 1 1 1 0 1 1 1 0 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 1 1 0 0 1 1 1 0 1 1 1 0 0 1 0 1 0 1 0 1 1 0 0 1 0 1 0 0 1 1 1 1 1 0 0 0 1 0 0 1 0 1 1 ...
result:
wrong answer 25th words differ - expected: '0', found: '1'