# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
78694 |
2018-10-07T16:23:39 Z |
tincamatei |
Seats (IOI18_seats) |
C++14 |
|
4000 ms |
112252 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;
inline 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);
}
inline void update(int i, int j, T val) {
updateDfs(i, j, val, 1, lInit, rInit);
}
inline T query(int i, int j) {
return queryDfs(i, j, 1, lInit, rInit);
}
};
const int MAX_N = 1000000;
struct Node {
int minVal, fr;
inline Node update(Node a, Node b, int x) {
a.minVal += b.minVal;
return a;
}
inline 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;
static inline 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});
}
static inline 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 |
156 ms |
48344 KB |
Output is correct |
2 |
Correct |
139 ms |
48344 KB |
Output is correct |
3 |
Correct |
160 ms |
48368 KB |
Output is correct |
4 |
Correct |
157 ms |
48484 KB |
Output is correct |
5 |
Correct |
107 ms |
48592 KB |
Output is correct |
6 |
Correct |
154 ms |
48592 KB |
Output is correct |
7 |
Correct |
177 ms |
48656 KB |
Output is correct |
8 |
Correct |
144 ms |
48656 KB |
Output is correct |
9 |
Correct |
140 ms |
48656 KB |
Output is correct |
10 |
Correct |
144 ms |
48656 KB |
Output is correct |
11 |
Correct |
129 ms |
48656 KB |
Output is correct |
12 |
Correct |
104 ms |
48656 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
156 ms |
48344 KB |
Output is correct |
2 |
Correct |
139 ms |
48344 KB |
Output is correct |
3 |
Correct |
160 ms |
48368 KB |
Output is correct |
4 |
Correct |
157 ms |
48484 KB |
Output is correct |
5 |
Correct |
107 ms |
48592 KB |
Output is correct |
6 |
Correct |
154 ms |
48592 KB |
Output is correct |
7 |
Correct |
177 ms |
48656 KB |
Output is correct |
8 |
Correct |
144 ms |
48656 KB |
Output is correct |
9 |
Correct |
140 ms |
48656 KB |
Output is correct |
10 |
Correct |
144 ms |
48656 KB |
Output is correct |
11 |
Correct |
129 ms |
48656 KB |
Output is correct |
12 |
Correct |
104 ms |
48656 KB |
Output is correct |
13 |
Correct |
185 ms |
48908 KB |
Output is correct |
14 |
Correct |
214 ms |
48908 KB |
Output is correct |
15 |
Correct |
140 ms |
48940 KB |
Output is correct |
16 |
Correct |
119 ms |
49212 KB |
Output is correct |
17 |
Correct |
164 ms |
49212 KB |
Output is correct |
18 |
Correct |
169 ms |
49212 KB |
Output is correct |
19 |
Correct |
161 ms |
49212 KB |
Output is correct |
20 |
Correct |
143 ms |
49212 KB |
Output is correct |
21 |
Correct |
129 ms |
49212 KB |
Output is correct |
22 |
Correct |
128 ms |
49224 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3408 ms |
77100 KB |
Output is correct |
2 |
Correct |
1820 ms |
77100 KB |
Output is correct |
3 |
Correct |
1653 ms |
77180 KB |
Output is correct |
4 |
Correct |
1421 ms |
77180 KB |
Output is correct |
5 |
Correct |
1577 ms |
77180 KB |
Output is correct |
6 |
Correct |
1436 ms |
77180 KB |
Output is correct |
7 |
Correct |
1643 ms |
77180 KB |
Output is correct |
8 |
Correct |
1742 ms |
77180 KB |
Output is correct |
9 |
Correct |
1717 ms |
77180 KB |
Output is correct |
10 |
Correct |
1645 ms |
77180 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
182 ms |
77180 KB |
Output is correct |
2 |
Correct |
344 ms |
77180 KB |
Output is correct |
3 |
Correct |
1653 ms |
77180 KB |
Output is correct |
4 |
Correct |
3238 ms |
77180 KB |
Output is correct |
5 |
Correct |
1310 ms |
84864 KB |
Output is correct |
6 |
Correct |
3190 ms |
112252 KB |
Output is correct |
7 |
Correct |
1462 ms |
112252 KB |
Output is correct |
8 |
Correct |
1809 ms |
112252 KB |
Output is correct |
9 |
Correct |
1688 ms |
112252 KB |
Output is correct |
10 |
Correct |
1542 ms |
112252 KB |
Output is correct |
11 |
Correct |
1481 ms |
112252 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
624 ms |
112252 KB |
Output is correct |
2 |
Correct |
633 ms |
112252 KB |
Output is correct |
3 |
Correct |
629 ms |
112252 KB |
Output is correct |
4 |
Correct |
673 ms |
112252 KB |
Output is correct |
5 |
Correct |
790 ms |
112252 KB |
Output is correct |
6 |
Correct |
2199 ms |
112252 KB |
Output is correct |
7 |
Correct |
2614 ms |
112252 KB |
Output is correct |
8 |
Correct |
2130 ms |
112252 KB |
Output is correct |
9 |
Execution timed out |
4033 ms |
112252 KB |
Time limit exceeded |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
156 ms |
48344 KB |
Output is correct |
2 |
Correct |
139 ms |
48344 KB |
Output is correct |
3 |
Correct |
160 ms |
48368 KB |
Output is correct |
4 |
Correct |
157 ms |
48484 KB |
Output is correct |
5 |
Correct |
107 ms |
48592 KB |
Output is correct |
6 |
Correct |
154 ms |
48592 KB |
Output is correct |
7 |
Correct |
177 ms |
48656 KB |
Output is correct |
8 |
Correct |
144 ms |
48656 KB |
Output is correct |
9 |
Correct |
140 ms |
48656 KB |
Output is correct |
10 |
Correct |
144 ms |
48656 KB |
Output is correct |
11 |
Correct |
129 ms |
48656 KB |
Output is correct |
12 |
Correct |
104 ms |
48656 KB |
Output is correct |
13 |
Correct |
185 ms |
48908 KB |
Output is correct |
14 |
Correct |
214 ms |
48908 KB |
Output is correct |
15 |
Correct |
140 ms |
48940 KB |
Output is correct |
16 |
Correct |
119 ms |
49212 KB |
Output is correct |
17 |
Correct |
164 ms |
49212 KB |
Output is correct |
18 |
Correct |
169 ms |
49212 KB |
Output is correct |
19 |
Correct |
161 ms |
49212 KB |
Output is correct |
20 |
Correct |
143 ms |
49212 KB |
Output is correct |
21 |
Correct |
129 ms |
49212 KB |
Output is correct |
22 |
Correct |
128 ms |
49224 KB |
Output is correct |
23 |
Correct |
3408 ms |
77100 KB |
Output is correct |
24 |
Correct |
1820 ms |
77100 KB |
Output is correct |
25 |
Correct |
1653 ms |
77180 KB |
Output is correct |
26 |
Correct |
1421 ms |
77180 KB |
Output is correct |
27 |
Correct |
1577 ms |
77180 KB |
Output is correct |
28 |
Correct |
1436 ms |
77180 KB |
Output is correct |
29 |
Correct |
1643 ms |
77180 KB |
Output is correct |
30 |
Correct |
1742 ms |
77180 KB |
Output is correct |
31 |
Correct |
1717 ms |
77180 KB |
Output is correct |
32 |
Correct |
1645 ms |
77180 KB |
Output is correct |
33 |
Correct |
182 ms |
77180 KB |
Output is correct |
34 |
Correct |
344 ms |
77180 KB |
Output is correct |
35 |
Correct |
1653 ms |
77180 KB |
Output is correct |
36 |
Correct |
3238 ms |
77180 KB |
Output is correct |
37 |
Correct |
1310 ms |
84864 KB |
Output is correct |
38 |
Correct |
3190 ms |
112252 KB |
Output is correct |
39 |
Correct |
1462 ms |
112252 KB |
Output is correct |
40 |
Correct |
1809 ms |
112252 KB |
Output is correct |
41 |
Correct |
1688 ms |
112252 KB |
Output is correct |
42 |
Correct |
1542 ms |
112252 KB |
Output is correct |
43 |
Correct |
1481 ms |
112252 KB |
Output is correct |
44 |
Correct |
624 ms |
112252 KB |
Output is correct |
45 |
Correct |
633 ms |
112252 KB |
Output is correct |
46 |
Correct |
629 ms |
112252 KB |
Output is correct |
47 |
Correct |
673 ms |
112252 KB |
Output is correct |
48 |
Correct |
790 ms |
112252 KB |
Output is correct |
49 |
Correct |
2199 ms |
112252 KB |
Output is correct |
50 |
Correct |
2614 ms |
112252 KB |
Output is correct |
51 |
Correct |
2130 ms |
112252 KB |
Output is correct |
52 |
Execution timed out |
4033 ms |
112252 KB |
Time limit exceeded |
53 |
Halted |
0 ms |
0 KB |
- |