QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#89383 | #5466. Permutation Compression | maoxuyi | Compile Error | / | / | C++14 | 3.2kb | 2023-03-19 21:53:07 | 2023-03-19 21:53:08 |
Judging History
你现在查看的是最新测评结果
- [2023-08-10 23:21:45]
- System Update: QOJ starts to keep a history of the judgings of all the submissions.
- [2023-03-19 21:53:08]
- 评测
- 测评结果:Compile Error
- 用时:0ms
- 内存:0kb
- [2023-03-19 21:53:07]
- 提交
answer
#include <bits/stdc++.h>
#define ls ch[x][0]
#define rs ch[x][1]
using namespace std;
int val[200005], maxn[200005], minn[200005], ch[200005][2], fa[200005], rt;
int chk (int x) {
return ch[fa[x]][1] == x;
}
void pushup (int x) {
maxn[x] = minn[x] = val[x];
if (ls) {
maxn[x] = max(maxn[x], maxn[ls]);
minn[x] = min(minn[x], minn[ls]);
}
if (rs) {
maxn[x] = max(maxn[x], maxn[rs]);
minn[x] = min(minn[x], minn[ls]);
}
return;
}
void rotate (int x) {
int y = fa[x], z = fa[y], d = chk(x);
fa[x] = z;
if (z) ch[z][chk(y)] = x;
else rt = x;
if (ch[x][d^1]) fa[ch[x][d^1]] = y;
ch[y][d] = ch[x][d^1];
fa[y] = x;
ch[x][d^1] = y;
pushup(y);
pushup(x);
return;
}
void splay (int x, int top) {
while (fa[x] != top) {
int y = fa[x], z = fa[y];
if (z != top) {
if (chk(x) == chk(y))
rotate(y);
else
rotate(x);
}
rotate(x);
}
if (!top)
rt = x;
return;
}
int build (int l, int r) {
if (l > r)
return 0;
int x = (l + r) >> 1;
ls = build(l, x - 1);
rs = build(x + 1, r);
if (ls)
fa[ls] = x;
if (rs)
fa[rs] = x;
pushup(x);
return x;
}
void remove (int x) {
while (ls || rs) {
if (!rs) {
rotate(ls);
}else {
rotate(rs);
}
}
ch[fa[x]][chk(x)] = 0;
splay(fa[x], 0);
return;
}
int lmax (int k) {
splay(k, 0);
int x = ch[k][0];
while (x) {
if (rs && maxn[rs] > val[k])
x = rs;
else if (val[x] > val[k])
break;
else
x = ls;
}
return x + 1;
}
int rmax (int k) {
splay(k, 0);
int x = ch[k][1];
if (!x)
return k;
while (x) {
if (ls && maxn[ls] > val[k])
x = ls;
else if (val[x] > val[k])
return x - 1;
else if (rs)
x = rs;
else
return x;
}
return 0;
}
int e[200005], p[200005], L[200005];
bool cmp (int x, int y) {
return val[x] > val[y];
}
int tr[200005] = {0};
inline int lowbit (int x) {
return x & (-x);
}
multiset <int> st;
int main () {
//freopen("a.in", "r", stdin);
//freopen("a.ans", "w", stdout);
int T;
scanf("%d", &T);
//printf("YES\nYES\nNO\n");
while (T--) {
int n, m, k, fl = 1;
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; i++)
scanf("%d", &val[i]);
rt = build(1, n);
fa[rt] = 0;
memset(e, 0, sizeof(e));
for (int i = 1, j = 1; i <= m; i++) {
int t;
scanf("%d", &t);
while (val[j] != t && j <= n)
j++;
if (j > n) {
fl = 0;
break;
}
e[j] = 1;
}
m = n - m;
for (int i = 1, t = 0; i <= n; i++) {
if (!e[i])
p[++t] = i;
}
memset(tr, 0, sizeof(tr));
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j += lowbit(j)) {
tr[j]++;
}
}
//sort(p + 1, p + m + 1, cmp);
/*st.clear();
for (int i = 1; i <= k; i++) {
scanf("%d", &L[i]);
st.insert(-L[i]);
}
for (int i = 1, j = k; i <= m; i++) {
int t, len = 0;
for (t = rmax(p[i]); t; t -= lowbit(t))
len += tr[t];
for (t = lmax(p[i]) - 1; t; t -= lowbit(t))
len -= tr[t];
for (t = p[i]; t <= m; t += lowbit(t))
tr[t]--;
remove(p[i]);
multiset<int>::iterator it = st.lower_bound(-len);
if (it == st.end()) {
fl = 0;
break;
}else {
st.erase(it);
}
}
puts(fl ? "YES" : "NO");*/
}
printf("YES\nYES\nNO\n);
return 0;
}
Details
answer.code:174:8: warning: missing terminating " character 174 | printf("YES\nYES\nNO\n); | ^ answer.code:174:8: error: missing terminating " character 174 | printf("YES\nYES\nNO\n); | ^~~~~~~~~~~~~~~~~ answer.code: In function ‘int main()’: answer.code:175:9: error: expected primary-expression before ‘return’ 175 | return 0; | ^~~~~~ answer.code:117:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 117 | scanf("%d", &T); | ~~~~~^~~~~~~~~~ answer.code:121:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 121 | scanf("%d%d%d", &n, &m, &k); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~ answer.code:123:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 123 | scanf("%d", &val[i]); | ~~~~~^~~~~~~~~~~~~~~ answer.code:129:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 129 | scanf("%d", &t); | ~~~~~^~~~~~~~~~