# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
78693 |
2018-10-07T16:13:48 Z |
tincamatei |
Seats (IOI18_seats) |
C++14 |
|
4000 ms |
139476 KB |
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
template<int n, typename T, typename Updater>
class LazyAint {
private:
T neutralUpd, neutralQry, initval;
T *aint;
T *lazy;
Updater upd;
int lInit, rInit;
void pushlazy(int nod, int l, int r) {
aint[nod] = upd.update(aint[nod], lazy[nod], r - l + 1);
if(2 * nod <= 4 * n)
lazy[2 * nod] = upd.update(lazy[2 * nod], lazy[nod], r - l + 1);
if(2 * nod + 1 <= 4 * n)
lazy[2 * nod + 1] = upd.update(lazy[2 * nod + 1], lazy[nod], r - l + 1);
lazy[nod] = neutralUpd;
}
void updateDfs(int i, int j, T val, int nod = 1, int l = 1, int r = n) {
pushlazy(nod, l, r);
if(r < i || j < l || r < l || j < i)
return ;
if(i <= l && r <= j) {
lazy[nod] = upd.update(lazy[nod], val, r - l + 1);
pushlazy(nod, l, r);
return;
}
int mid = (l + r) / 2;
if(l < r) {
updateDfs(i, j, val, 2 * nod, l, mid);
updateDfs(i, j, val, 2 * nod + 1, mid + 1, r);
aint[nod] = upd.query(aint[2 * nod], aint[2 * nod + 1]);
}
}
T queryDfs(int i, int j, int nod = 1, int l = 1, int r = n) {
if(r < i || j < l || r < l || j < i)
return neutralQry;
pushlazy(nod, l, r);
if(i <= l && r <= j)
return aint[nod];
int mid = (l + r) / 2;
return upd.query(queryDfs(i, j, 2 * nod, l, mid),
queryDfs(i, j, 2 * nod + 1, mid + 1, r));
}
void initDfs(int nod, int l, int r) {
int mid = (l + r) / 2;
if(l < r) {
initDfs(2 * nod, l, mid);
initDfs(2 * nod + 1, mid + 1, r);
aint[nod] = upd.query(aint[2 * nod], aint[2 * nod + 1]);
} else
aint[nod] = initval;
}
public:
LazyAint(T _neutralUpd, T _neutralQry, T _initval, int _lInit = 1, int _rInit = n) {
neutralUpd = _neutralUpd;
neutralQry = _neutralQry;
initval = _initval;
lInit = _lInit;
rInit = _rInit;
aint = new T[1 + 4 * n];
lazy = new T[1 + 4 * n];
for(int i = 0; i <= 4 * n; ++i)
lazy[i] = neutralUpd;
initDfs(1, lInit, rInit);
}
void update(int i, int j, T val) {
updateDfs(i, j, val, 1, lInit, rInit);
}
T query(int i, int j) {
return queryDfs(i, j, 1, lInit, rInit);
}
};
const int MAX_N = 1000000;
struct Node {
int minVal, fr;
Node update(Node a, Node b, int x) {
a.minVal += b.minVal;
return a;
}
Node query(Node a, Node b) {
if(b.minVal < a.minVal) {
a.minVal = b.minVal;
a.fr = b.fr;
} else if(b.minVal == a.minVal)
a.fr += b.fr;
return a;
}
};
LazyAint<1+MAX_N, Node, Node> aint({0, 0}, {MAX_N + 1, 0}, {0, 1}, 0, MAX_N);
int N;
int cells[4];
int **matr;
vector<int> R, C;
void activateSqr(int l, int c, int x) {
cells[0] = matr[l][c];
cells[1] = matr[l + 1][c];
cells[2] = matr[l][c + 1];
cells[3] = matr[l + 1][c + 1];
std::sort(cells, cells + 4);
aint.update(cells[0], cells[1] - 1, {x, 0});
aint.update(cells[2], cells[3] - 1, {4 * x, 0});
}
void activateCells(int l, int c, int x) {
activateSqr(l, c, x);
activateSqr(l - 1, c, x);
activateSqr(l, c - 1, x);
activateSqr(l - 1, c - 1, x);
}
void give_initial_chart(int H, int W, std::vector<int> _R, std::vector<int> _C) {
N = H * W;
R = _R;
C = _C;
matr = new int*[1 + H + 1];
for(int i = 0; i <= H + 1; ++i) {
matr[i] = new int[1 + W + 1];
for(int j = 0; j <= W + 1; ++j)
matr[i][j] = N;
}
for(int i = 0; i < N; ++i) {
R[i]++;
C[i]++;
matr[R[i]][C[i]] = i;
}
for(int i = 0; i <= H; ++i)
for(int j = 0; j <= W; ++j)
activateSqr(i, j, 1);
}
int swap_seats(int a, int b) {
activateCells(R[a], C[a], -1);
activateCells(R[b], C[b], -1);
swap(R[a], R[b]);
swap(C[a], C[b]);
swap(matr[R[a]][C[a]], matr[R[b]][C[b]]);
activateCells(R[a], C[a], 1);
activateCells(R[b], C[b], 1);
Node x = aint.query(0, N - 1);
if(x.minVal != 4)
return 0;
return x.fr;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
123 ms |
48348 KB |
Output is correct |
2 |
Correct |
133 ms |
48448 KB |
Output is correct |
3 |
Correct |
155 ms |
48540 KB |
Output is correct |
4 |
Correct |
102 ms |
48540 KB |
Output is correct |
5 |
Correct |
118 ms |
48540 KB |
Output is correct |
6 |
Correct |
131 ms |
48544 KB |
Output is correct |
7 |
Correct |
147 ms |
48544 KB |
Output is correct |
8 |
Correct |
146 ms |
48664 KB |
Output is correct |
9 |
Correct |
162 ms |
48664 KB |
Output is correct |
10 |
Correct |
140 ms |
48664 KB |
Output is correct |
11 |
Correct |
128 ms |
48664 KB |
Output is correct |
12 |
Correct |
101 ms |
48664 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
123 ms |
48348 KB |
Output is correct |
2 |
Correct |
133 ms |
48448 KB |
Output is correct |
3 |
Correct |
155 ms |
48540 KB |
Output is correct |
4 |
Correct |
102 ms |
48540 KB |
Output is correct |
5 |
Correct |
118 ms |
48540 KB |
Output is correct |
6 |
Correct |
131 ms |
48544 KB |
Output is correct |
7 |
Correct |
147 ms |
48544 KB |
Output is correct |
8 |
Correct |
146 ms |
48664 KB |
Output is correct |
9 |
Correct |
162 ms |
48664 KB |
Output is correct |
10 |
Correct |
140 ms |
48664 KB |
Output is correct |
11 |
Correct |
128 ms |
48664 KB |
Output is correct |
12 |
Correct |
101 ms |
48664 KB |
Output is correct |
13 |
Correct |
179 ms |
48832 KB |
Output is correct |
14 |
Correct |
205 ms |
48832 KB |
Output is correct |
15 |
Correct |
136 ms |
48908 KB |
Output is correct |
16 |
Correct |
119 ms |
49176 KB |
Output is correct |
17 |
Correct |
156 ms |
49176 KB |
Output is correct |
18 |
Correct |
153 ms |
49176 KB |
Output is correct |
19 |
Correct |
156 ms |
49176 KB |
Output is correct |
20 |
Correct |
136 ms |
49176 KB |
Output is correct |
21 |
Correct |
117 ms |
49176 KB |
Output is correct |
22 |
Correct |
125 ms |
49208 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3293 ms |
81560 KB |
Output is correct |
2 |
Correct |
1718 ms |
81592 KB |
Output is correct |
3 |
Correct |
1637 ms |
81592 KB |
Output is correct |
4 |
Correct |
1421 ms |
81592 KB |
Output is correct |
5 |
Correct |
1490 ms |
81592 KB |
Output is correct |
6 |
Correct |
1388 ms |
81596 KB |
Output is correct |
7 |
Correct |
1495 ms |
81596 KB |
Output is correct |
8 |
Correct |
1630 ms |
81596 KB |
Output is correct |
9 |
Correct |
1666 ms |
81596 KB |
Output is correct |
10 |
Correct |
1588 ms |
81596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
176 ms |
81596 KB |
Output is correct |
2 |
Correct |
319 ms |
81596 KB |
Output is correct |
3 |
Correct |
1460 ms |
81612 KB |
Output is correct |
4 |
Correct |
3492 ms |
81612 KB |
Output is correct |
5 |
Correct |
1324 ms |
89420 KB |
Output is correct |
6 |
Correct |
3321 ms |
116684 KB |
Output is correct |
7 |
Correct |
1436 ms |
116684 KB |
Output is correct |
8 |
Correct |
1938 ms |
116684 KB |
Output is correct |
9 |
Correct |
1611 ms |
116684 KB |
Output is correct |
10 |
Correct |
1608 ms |
116684 KB |
Output is correct |
11 |
Correct |
1501 ms |
116684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
622 ms |
116684 KB |
Output is correct |
2 |
Correct |
607 ms |
116684 KB |
Output is correct |
3 |
Correct |
596 ms |
116684 KB |
Output is correct |
4 |
Correct |
616 ms |
116684 KB |
Output is correct |
5 |
Correct |
724 ms |
116684 KB |
Output is correct |
6 |
Correct |
2161 ms |
116684 KB |
Output is correct |
7 |
Correct |
2559 ms |
116684 KB |
Output is correct |
8 |
Correct |
2102 ms |
122888 KB |
Output is correct |
9 |
Execution timed out |
4019 ms |
139476 KB |
Time limit exceeded |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
123 ms |
48348 KB |
Output is correct |
2 |
Correct |
133 ms |
48448 KB |
Output is correct |
3 |
Correct |
155 ms |
48540 KB |
Output is correct |
4 |
Correct |
102 ms |
48540 KB |
Output is correct |
5 |
Correct |
118 ms |
48540 KB |
Output is correct |
6 |
Correct |
131 ms |
48544 KB |
Output is correct |
7 |
Correct |
147 ms |
48544 KB |
Output is correct |
8 |
Correct |
146 ms |
48664 KB |
Output is correct |
9 |
Correct |
162 ms |
48664 KB |
Output is correct |
10 |
Correct |
140 ms |
48664 KB |
Output is correct |
11 |
Correct |
128 ms |
48664 KB |
Output is correct |
12 |
Correct |
101 ms |
48664 KB |
Output is correct |
13 |
Correct |
179 ms |
48832 KB |
Output is correct |
14 |
Correct |
205 ms |
48832 KB |
Output is correct |
15 |
Correct |
136 ms |
48908 KB |
Output is correct |
16 |
Correct |
119 ms |
49176 KB |
Output is correct |
17 |
Correct |
156 ms |
49176 KB |
Output is correct |
18 |
Correct |
153 ms |
49176 KB |
Output is correct |
19 |
Correct |
156 ms |
49176 KB |
Output is correct |
20 |
Correct |
136 ms |
49176 KB |
Output is correct |
21 |
Correct |
117 ms |
49176 KB |
Output is correct |
22 |
Correct |
125 ms |
49208 KB |
Output is correct |
23 |
Correct |
3293 ms |
81560 KB |
Output is correct |
24 |
Correct |
1718 ms |
81592 KB |
Output is correct |
25 |
Correct |
1637 ms |
81592 KB |
Output is correct |
26 |
Correct |
1421 ms |
81592 KB |
Output is correct |
27 |
Correct |
1490 ms |
81592 KB |
Output is correct |
28 |
Correct |
1388 ms |
81596 KB |
Output is correct |
29 |
Correct |
1495 ms |
81596 KB |
Output is correct |
30 |
Correct |
1630 ms |
81596 KB |
Output is correct |
31 |
Correct |
1666 ms |
81596 KB |
Output is correct |
32 |
Correct |
1588 ms |
81596 KB |
Output is correct |
33 |
Correct |
176 ms |
81596 KB |
Output is correct |
34 |
Correct |
319 ms |
81596 KB |
Output is correct |
35 |
Correct |
1460 ms |
81612 KB |
Output is correct |
36 |
Correct |
3492 ms |
81612 KB |
Output is correct |
37 |
Correct |
1324 ms |
89420 KB |
Output is correct |
38 |
Correct |
3321 ms |
116684 KB |
Output is correct |
39 |
Correct |
1436 ms |
116684 KB |
Output is correct |
40 |
Correct |
1938 ms |
116684 KB |
Output is correct |
41 |
Correct |
1611 ms |
116684 KB |
Output is correct |
42 |
Correct |
1608 ms |
116684 KB |
Output is correct |
43 |
Correct |
1501 ms |
116684 KB |
Output is correct |
44 |
Correct |
622 ms |
116684 KB |
Output is correct |
45 |
Correct |
607 ms |
116684 KB |
Output is correct |
46 |
Correct |
596 ms |
116684 KB |
Output is correct |
47 |
Correct |
616 ms |
116684 KB |
Output is correct |
48 |
Correct |
724 ms |
116684 KB |
Output is correct |
49 |
Correct |
2161 ms |
116684 KB |
Output is correct |
50 |
Correct |
2559 ms |
116684 KB |
Output is correct |
51 |
Correct |
2102 ms |
122888 KB |
Output is correct |
52 |
Execution timed out |
4019 ms |
139476 KB |
Time limit exceeded |
53 |
Halted |
0 ms |
0 KB |
- |