| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 117932 |
2019-06-17T12:52:49 Z |
imyujin |
Tenis (COI19_tenis) |
C++14 |
|
81 ms |
5240 KB |
#include<stdio.h>
#include<algorithm>
using namespace std;
#define MAXN 100005
#define MAXQ 11
int N, Q;
int r[3][MAXN];
int idx[3][MAXN];
bool chk[MAXN];
int seg[3 * MAXN], lazy[3 * MAXN];
int minidx(int x) {
return idx[0][x] < idx[1][x] ? (idx[0][x] < idx[2][x] ? idx[0][x] : idx[2][x]) : (idx[1][x] < idx[2][x] ? idx[1][x] : idx[2][x]);
}
int maxidx(int x) {
return idx[0][x] > idx[1][x] ? (idx[0][x] > idx[2][x] ? idx[0][x] : idx[2][x]) : (idx[1][x] > idx[2][x] ? idx[1][x] : idx[2][x]);
}
int findzero(int x, int idx, int l, int r) {
if (l == r) return seg[idx] + lazy[idx] == 0 ? l : l - 1;
seg[idx] += lazy[idx];
lazy[idx * 2] += lazy[idx];
lazy[idx * 2 + 1] += lazy[idx];
lazy[idx] = 0;
int m = (l + r) / 2;
if (x <= m) return findzero(x, idx * 2, l, m);
int t = findzero(x, idx * 2 + 1, m + 1, r);
return t == m ? findzero(x, idx * 2, l, m) : t;
}
void updseg(int a, int b, int c, int idx, int l, int r) {
//printf("(%d %d %d %d)\n", l, r, seg[idx], lazy[idx]);
if (a > b) return;
if (a <= l && r <= b) lazy[idx] += c;
else if (a <= r && l <= b) {
int m = (l + r) / 2;
updseg(a, b, c, idx * 2, l, m);
updseg(a, b, c, idx * 2 + 1, m + 1, r);
seg[idx] = seg[idx * 2] < seg[idx * 2 + 1] ? seg[idx * 2] : seg[idx * 2 + 1];
}
seg[idx] += lazy[idx];
lazy[idx * 2] += lazy[idx];
lazy[idx * 2 + 1] += lazy[idx];
lazy[idx] = 0;
}
int main() {
int T[11], X[11], P[11], A[11], B[11];
//freopen("input.txt", "r", stdin);
scanf("%d%d", &N, &Q);
for (int i = 0; i < 3; i++) for (int j = 0; j < N; j++) scanf("%d", &r[i][j]);
for (int i = 0; i < Q; i++) {
scanf("%d", T + i);
if (T[i] == 1) scanf("%d", X + i);
else scanf("%d%d%d", P + i, A + i, B + i);
}
for (int i = 0; i < 3; i++) for (int j = 0; j < N; j++) idx[i][r[i][j]] = j;
//for (int i = 1; i <= N; i++) printf("[%d %d]\n", minidx(i), maxidx(i));
for (int i = 1; i <= N; i++) {
updseg(minidx(i) + 1, maxidx(i), 1, 1, 0, N - 1);
//for (int j = 1; j < 2 * N; j ++) printf("%d %d\n", seg[j], lazy[j]);
//printf("##\n");
}
for (int i = 0; i < Q; i++) {
//for (int j = 1; j < 2 * N; j++) printf("%d %d\n", seg[j], lazy[j]);
//printf("*\n");
if (T[i] == 1) {
if(findzero(idx[0][X[i]], 1, 0, N-1)==0) printf("DA\n");
else printf("NE\n");
}
else {
updseg(minidx(A[i]) + 1, maxidx(A[i]), -1, 1, 0, N - 1);
updseg(minidx(B[i]) + 1, maxidx(B[i]), -1, 1, 0, N - 1);
//printf("@@@%d %d\n", idx[P[i]][A[i]], idx[P[i]][B[i]]);
swap(idx[P[i]-1][A[i]], idx[P[i]-1][B[i]]);
//for (int j = 1; j < 2 * N; j++) printf("%d %d\n", seg[j], lazy[j]);
//printf("%d %d %d %d\n", minidx(A[i]), maxidx(A[i]), minidx(B[i]), maxidx(B[i]));
//printf("%d %d\n", idx[P[i]][A[i]], idx[P[i]][B[i]]);
updseg(minidx(A[i]) + 1, maxidx(A[i]), 1, 1, 0, N - 1);
updseg(minidx(B[i]) + 1, maxidx(B[i]), 1, 1, 0, N - 1);
}
}
return 0;
}
Compilation message
tenis.cpp: In function 'int main()':
tenis.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &Q);
~~~~~^~~~~~~~~~~~~~~~
tenis.cpp:57:63: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (int i = 0; i < 3; i++) for (int j = 0; j < N; j++) scanf("%d", &r[i][j]);
~~~~~^~~~~~~~~~~~~~~~
tenis.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", T + i);
~~~~~^~~~~~~~~~~~~
tenis.cpp:60:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
if (T[i] == 1) scanf("%d", X + i);
~~~~~^~~~~~~~~~~~~
tenis.cpp:61:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
else scanf("%d%d%d", P + i, A + i, B + i);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| 6 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| 6 |
Correct |
2 ms |
384 KB |
Output is correct |
| 7 |
Correct |
2 ms |
384 KB |
Output is correct |
| 8 |
Correct |
2 ms |
384 KB |
Output is correct |
| 9 |
Correct |
2 ms |
432 KB |
Output is correct |
| 10 |
Correct |
2 ms |
384 KB |
Output is correct |
| 11 |
Correct |
2 ms |
412 KB |
Output is correct |
| 12 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| 6 |
Correct |
2 ms |
384 KB |
Output is correct |
| 7 |
Correct |
2 ms |
384 KB |
Output is correct |
| 8 |
Correct |
2 ms |
384 KB |
Output is correct |
| 9 |
Correct |
2 ms |
432 KB |
Output is correct |
| 10 |
Correct |
2 ms |
384 KB |
Output is correct |
| 11 |
Correct |
2 ms |
412 KB |
Output is correct |
| 12 |
Correct |
2 ms |
384 KB |
Output is correct |
| 13 |
Incorrect |
81 ms |
5240 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
39 ms |
2924 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| 6 |
Correct |
2 ms |
384 KB |
Output is correct |
| 7 |
Correct |
2 ms |
384 KB |
Output is correct |
| 8 |
Correct |
2 ms |
384 KB |
Output is correct |
| 9 |
Correct |
2 ms |
432 KB |
Output is correct |
| 10 |
Correct |
2 ms |
384 KB |
Output is correct |
| 11 |
Correct |
2 ms |
412 KB |
Output is correct |
| 12 |
Correct |
2 ms |
384 KB |
Output is correct |
| 13 |
Incorrect |
81 ms |
5240 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
