| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 157821 |
2019-10-13T08:03:35 Z |
imyujin |
Tenis (COI19_tenis) |
C++17 |
|
86 ms |
8440 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
const int MAXN = 100010;
const int MX = 1 << 17;
int N, Q;
int A[3][MAXN];
int idx[3][MAXN];
lint s[MAXN];
lint seg[2 * MX], lazy[2 * MX];
void mkseg(int idx, int l, int r) {
if(l == r) seg[idx] = s[l] - (lint)l * (l + 1);
else {
int m = (l + r) / 2;
mkseg(idx * 2, l, m);
mkseg(idx * 2 + 1, m + 1, r);
seg[idx] = min(seg[idx * 2], seg[idx * 2 + 1]);
}
}
void spreadlazy(int idx) {
seg[idx * 2] += lazy[idx];
seg[idx * 2 + 1] += lazy[idx];
lazy[idx * 2] += lazy[idx];
lazy[idx * 2 + 1] += lazy[idx];
lazy[idx] = 0;
}
int gseg(int idx, int l, int r) {
if(seg[idx] > 0) return -1;
if(l == r) return l;
int m = (l + r) / 2;
spreadlazy(idx);
int t = gseg(idx * 2, l, m);
return t == -1 ? gseg(idx * 2 + 1, m + 1, r) : t;
}
void updseg(int idx, int l, int r, int x, int z) {
if(x <= l) {
seg[idx] += z;
lazy[idx] += z;
}
else if(x <= r) {
int m = (l + r) / 2;
updseg(idx * 2, l, m, x, z);
updseg(idx * 2 + 1, m + 1, r, x, z);
}
}
void updseg(int x, int z) { updseg(1, 0, N - 1, x, z); }
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> N >> Q;
for(int i = 0; i < 3; i++) for(int j = 0; j < N; j++) cin >> A[i][j];
for(int i = 0; i < 3; i++) for(int j = 0; j < N; j++) idx[i][A[i][j]] = j;
for(int i = 0; i < N; i++)
s[i] = (i > 0 ? s[i - 1] : 0) + idx[0][A[1][i]] + idx[0][A[2][i]];
mkseg(1, 0, N - 1);
while(Q--) {
int c;
cin >> c;
if(c == 1) {
int x;
cin >> x;
int t = gseg(1, 0, N - 1);
cout << (idx[0][x] <= t ? "DA" : "NE") << "\n";
}
else {
int p, a, b;
cin >> p >> a >> b;
p--;
if(p == 0) {
for(int i = 1; i < 3; i++) {
updseg(idx[i][a], idx[0][b] - idx[0][a]);
updseg(idx[i][b], idx[0][a] - idx[0][b]);
}
swap(idx[0][a], idx[0][b]);
}
else {
updseg(idx[p][a], idx[0][b] - idx[0][a]);
updseg(idx[p][b], idx[0][a] - idx[0][b]);
swap(idx[p][a], idx[p][b]);
}
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
380 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
380 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
504 KB |
Output is correct |
| 8 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
380 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
504 KB |
Output is correct |
| 8 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
74 ms |
8440 KB |
Output is correct |
| 2 |
Correct |
79 ms |
8316 KB |
Output is correct |
| 3 |
Correct |
77 ms |
8312 KB |
Output is correct |
| 4 |
Correct |
83 ms |
8312 KB |
Output is correct |
| 5 |
Correct |
75 ms |
8412 KB |
Output is correct |
| 6 |
Correct |
86 ms |
8292 KB |
Output is correct |
| 7 |
Correct |
75 ms |
8388 KB |
Output is correct |
| 8 |
Correct |
86 ms |
8312 KB |
Output is correct |
| 9 |
Correct |
74 ms |
8420 KB |
Output is correct |
| 10 |
Correct |
76 ms |
8328 KB |
Output is correct |
| 11 |
Correct |
73 ms |
8440 KB |
Output is correct |
| 12 |
Correct |
77 ms |
8312 KB |
Output is correct |
| 13 |
Correct |
86 ms |
8380 KB |
Output is correct |
| 14 |
Correct |
75 ms |
8312 KB |
Output is correct |
| 15 |
Correct |
75 ms |
8284 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
380 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
504 KB |
Output is correct |
| 8 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
