# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
156914 |
2019-10-08T08:58:28 Z |
Alexa2001 |
Seats (IOI18_seats) |
C++17 |
|
2210 ms |
222096 KB |
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
const int Nmax = 1e6 + 5;
const int inf = 1e9;
typedef long long ll;
typedef pair<int,int> Pair;
ll mars[Nmax];
int N, M, P;
int posL[Nmax], posC[Nmax];
vector< vector<int> > matrix;
vector< vector< pair<Pair, Pair> > > coef;
///////////////////////////////////////////////////
struct info
{
ll mn; int cnt;
};
info operator + (info a, info b)
{
if(a.mn < b.mn) return a;
if(b.mn < a.mn) return b;
return {a.mn, a.cnt + b.cnt};
}
void operator += (info &a, ll b)
{
a.mn += b;
}
//////////////////////////////////////////////////
#define mid ((st+dr)>>1)
#define left_son ((node<<1))
#define right_son ((node<<1)|1)
class SegTree
{
info a[Nmax<<2];
ll lazy[Nmax<<2];
void propag(int node)
{
if(!lazy[node]) return;
lazy[left_son] += lazy[node];
lazy[right_son] += lazy[node];
a[left_son] += lazy[node];
a[right_son] += lazy[node];
lazy[node] = 0;
}
public:
void build(int node, int st, int dr, ll A[])
{
lazy[node] = 0;
if(st == dr)
{
a[node] = {A[st], 1};
return;
}
build(left_son, st, mid, A);
build(right_son, mid+1, dr, A);
a[node] = a[left_son] + a[right_son];
}
void update(int node, int st, int dr, int L, int R, int add)
{
if(L > R) return;
if(L <= st && dr <= R)
{
lazy[node] += add;
a[node] += add;
return;
}
propag(node);
if(L <= mid) update(left_son, st, mid, L, R, add);
if(mid < R) update(right_son, mid+1, dr, L, R, add);
a[node] = a[left_son] + a[right_son];
}
info query()
{
return a[1];
}
} aint;
pair<Pair, Pair> get_coef(int x, int y)
{
vector<int> aux;
aux.push_back(matrix[x][y]);
aux.push_back(matrix[x+1][y]);
aux.push_back(matrix[x][y+1]);
aux.push_back(matrix[x+1][y+1]);
sort(aux.begin(), aux.end());
return { {aux[0], aux[1] - 1}, {aux[2], aux[3] - 1} };
}
void add_mars(Pair a, int c)
{
mars[a.first] += c; mars[a.second+1] -= c;
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C)
{
N = H; M = W; P = N * M;
int i, j;
matrix.resize(N+2);
for(auto &it : matrix) it.resize(M+2, 0);
coef.resize(N+1);
for(auto &it : coef) it.resize(M+1);
for(i=0; i<=N+1; ++i)
for(j=0; j<=M+1; ++j)
matrix[i][j] = ( (1 <= i && i <= N && 1 <= j && j <= M) ? 0 : P);
for(i=0; i<P; ++i)
{
++R[i]; ++C[i];
posL[i] = R[i], posC[i] = C[i];
matrix[R[i]][C[i]] = i;
}
for(i=0; i<=N; ++i)
for(j=0; j<=M; ++j) /// ce coeficient are patratul cu coltul stanga-sus in (i,j) ?
coef[i][j] = get_coef(i, j);
for(i=0; i<=P; ++i) mars[i] = 0;
for(i=0; i<=N; ++i)
for(j=0; j<=M; ++j)
{
add_mars(coef[i][j].first, 1);
add_mars(coef[i][j].second, inf);
}
for(i=1; i<P; ++i)
mars[i] += mars[i-1];
aint.build(1, 0, P-1, mars);
}
int swap_seats(int id1, int id2)
{
int l1, c1, l2, c2;
l1 = posL[id1]; c1 = posC[id1];
l2 = posL[id2]; c2 = posC[id2];
vector<Pair> changes;
changes.push_back({l1, c1});
changes.push_back({l1-1, c1});
changes.push_back({l1, c1-1});
changes.push_back({l1-1, c1-1});
changes.push_back({l2, c2});
changes.push_back({l2-1, c2});
changes.push_back({l2, c2-1});
changes.push_back({l2-1, c2-1});
sort(changes.begin(), changes.end());
changes.erase( unique(changes.begin(), changes.end()), changes.end() );
swap(posL[id1], posL[id2]);
swap(posC[id1], posC[id2]);
swap(matrix[l1][c1], matrix[l2][c2]);
for(auto it : changes)
{
int pc, pl;
tie(pl, pc) = it;
auto C = coef[pl][pc];
aint.update(1, 0, P-1, C.first.first, C.first.second, -1);
aint.update(1, 0, P-1, C.second.first, C.second.second, -inf);
C = coef[pl][pc] = get_coef(pl, pc);
aint.update(1, 0, P-1, C.first.first, C.first.second, +1);
aint.update(1, 0, P-1, C.second.first, C.second.second, +inf);
}
auto res = aint.query();
assert(res.mn == 4);
return res.cnt;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
504 KB |
Output is correct |
2 |
Correct |
27 ms |
504 KB |
Output is correct |
3 |
Correct |
38 ms |
504 KB |
Output is correct |
4 |
Correct |
27 ms |
664 KB |
Output is correct |
5 |
Correct |
24 ms |
632 KB |
Output is correct |
6 |
Correct |
35 ms |
504 KB |
Output is correct |
7 |
Correct |
37 ms |
504 KB |
Output is correct |
8 |
Correct |
35 ms |
632 KB |
Output is correct |
9 |
Correct |
34 ms |
632 KB |
Output is correct |
10 |
Correct |
37 ms |
632 KB |
Output is correct |
11 |
Correct |
35 ms |
604 KB |
Output is correct |
12 |
Correct |
25 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
504 KB |
Output is correct |
2 |
Correct |
27 ms |
504 KB |
Output is correct |
3 |
Correct |
38 ms |
504 KB |
Output is correct |
4 |
Correct |
27 ms |
664 KB |
Output is correct |
5 |
Correct |
24 ms |
632 KB |
Output is correct |
6 |
Correct |
35 ms |
504 KB |
Output is correct |
7 |
Correct |
37 ms |
504 KB |
Output is correct |
8 |
Correct |
35 ms |
632 KB |
Output is correct |
9 |
Correct |
34 ms |
632 KB |
Output is correct |
10 |
Correct |
37 ms |
632 KB |
Output is correct |
11 |
Correct |
35 ms |
604 KB |
Output is correct |
12 |
Correct |
25 ms |
504 KB |
Output is correct |
13 |
Correct |
80 ms |
2040 KB |
Output is correct |
14 |
Correct |
88 ms |
1912 KB |
Output is correct |
15 |
Correct |
54 ms |
2168 KB |
Output is correct |
16 |
Correct |
45 ms |
2936 KB |
Output is correct |
17 |
Correct |
67 ms |
2040 KB |
Output is correct |
18 |
Correct |
60 ms |
1956 KB |
Output is correct |
19 |
Correct |
62 ms |
2024 KB |
Output is correct |
20 |
Correct |
56 ms |
2424 KB |
Output is correct |
21 |
Correct |
46 ms |
2300 KB |
Output is correct |
22 |
Correct |
46 ms |
2968 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
783 ms |
100564 KB |
Output is correct |
2 |
Correct |
673 ms |
100756 KB |
Output is correct |
3 |
Correct |
700 ms |
116548 KB |
Output is correct |
4 |
Correct |
667 ms |
116512 KB |
Output is correct |
5 |
Correct |
669 ms |
116744 KB |
Output is correct |
6 |
Correct |
651 ms |
116624 KB |
Output is correct |
7 |
Correct |
679 ms |
116600 KB |
Output is correct |
8 |
Correct |
679 ms |
116624 KB |
Output is correct |
9 |
Correct |
681 ms |
116588 KB |
Output is correct |
10 |
Correct |
660 ms |
116532 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
78 ms |
1912 KB |
Output is correct |
2 |
Correct |
134 ms |
12540 KB |
Output is correct |
3 |
Correct |
667 ms |
116768 KB |
Output is correct |
4 |
Correct |
845 ms |
116724 KB |
Output is correct |
5 |
Correct |
820 ms |
140152 KB |
Output is correct |
6 |
Correct |
1224 ms |
222096 KB |
Output is correct |
7 |
Correct |
708 ms |
124280 KB |
Output is correct |
8 |
Correct |
680 ms |
117016 KB |
Output is correct |
9 |
Correct |
672 ms |
117544 KB |
Output is correct |
10 |
Correct |
713 ms |
126692 KB |
Output is correct |
11 |
Correct |
831 ms |
167416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
114 ms |
2036 KB |
Output is correct |
2 |
Correct |
162 ms |
2104 KB |
Output is correct |
3 |
Correct |
231 ms |
2052 KB |
Output is correct |
4 |
Correct |
286 ms |
2224 KB |
Output is correct |
5 |
Correct |
459 ms |
3960 KB |
Output is correct |
6 |
Correct |
1388 ms |
128888 KB |
Output is correct |
7 |
Correct |
1421 ms |
128824 KB |
Output is correct |
8 |
Correct |
1394 ms |
128820 KB |
Output is correct |
9 |
Correct |
1702 ms |
128812 KB |
Output is correct |
10 |
Correct |
1275 ms |
128768 KB |
Output is correct |
11 |
Correct |
1274 ms |
124752 KB |
Output is correct |
12 |
Correct |
1308 ms |
124508 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
504 KB |
Output is correct |
2 |
Correct |
27 ms |
504 KB |
Output is correct |
3 |
Correct |
38 ms |
504 KB |
Output is correct |
4 |
Correct |
27 ms |
664 KB |
Output is correct |
5 |
Correct |
24 ms |
632 KB |
Output is correct |
6 |
Correct |
35 ms |
504 KB |
Output is correct |
7 |
Correct |
37 ms |
504 KB |
Output is correct |
8 |
Correct |
35 ms |
632 KB |
Output is correct |
9 |
Correct |
34 ms |
632 KB |
Output is correct |
10 |
Correct |
37 ms |
632 KB |
Output is correct |
11 |
Correct |
35 ms |
604 KB |
Output is correct |
12 |
Correct |
25 ms |
504 KB |
Output is correct |
13 |
Correct |
80 ms |
2040 KB |
Output is correct |
14 |
Correct |
88 ms |
1912 KB |
Output is correct |
15 |
Correct |
54 ms |
2168 KB |
Output is correct |
16 |
Correct |
45 ms |
2936 KB |
Output is correct |
17 |
Correct |
67 ms |
2040 KB |
Output is correct |
18 |
Correct |
60 ms |
1956 KB |
Output is correct |
19 |
Correct |
62 ms |
2024 KB |
Output is correct |
20 |
Correct |
56 ms |
2424 KB |
Output is correct |
21 |
Correct |
46 ms |
2300 KB |
Output is correct |
22 |
Correct |
46 ms |
2968 KB |
Output is correct |
23 |
Correct |
783 ms |
100564 KB |
Output is correct |
24 |
Correct |
673 ms |
100756 KB |
Output is correct |
25 |
Correct |
700 ms |
116548 KB |
Output is correct |
26 |
Correct |
667 ms |
116512 KB |
Output is correct |
27 |
Correct |
669 ms |
116744 KB |
Output is correct |
28 |
Correct |
651 ms |
116624 KB |
Output is correct |
29 |
Correct |
679 ms |
116600 KB |
Output is correct |
30 |
Correct |
679 ms |
116624 KB |
Output is correct |
31 |
Correct |
681 ms |
116588 KB |
Output is correct |
32 |
Correct |
660 ms |
116532 KB |
Output is correct |
33 |
Correct |
78 ms |
1912 KB |
Output is correct |
34 |
Correct |
134 ms |
12540 KB |
Output is correct |
35 |
Correct |
667 ms |
116768 KB |
Output is correct |
36 |
Correct |
845 ms |
116724 KB |
Output is correct |
37 |
Correct |
820 ms |
140152 KB |
Output is correct |
38 |
Correct |
1224 ms |
222096 KB |
Output is correct |
39 |
Correct |
708 ms |
124280 KB |
Output is correct |
40 |
Correct |
680 ms |
117016 KB |
Output is correct |
41 |
Correct |
672 ms |
117544 KB |
Output is correct |
42 |
Correct |
713 ms |
126692 KB |
Output is correct |
43 |
Correct |
831 ms |
167416 KB |
Output is correct |
44 |
Correct |
114 ms |
2036 KB |
Output is correct |
45 |
Correct |
162 ms |
2104 KB |
Output is correct |
46 |
Correct |
231 ms |
2052 KB |
Output is correct |
47 |
Correct |
286 ms |
2224 KB |
Output is correct |
48 |
Correct |
459 ms |
3960 KB |
Output is correct |
49 |
Correct |
1388 ms |
128888 KB |
Output is correct |
50 |
Correct |
1421 ms |
128824 KB |
Output is correct |
51 |
Correct |
1394 ms |
128820 KB |
Output is correct |
52 |
Correct |
1702 ms |
128812 KB |
Output is correct |
53 |
Correct |
1275 ms |
128768 KB |
Output is correct |
54 |
Correct |
1274 ms |
124752 KB |
Output is correct |
55 |
Correct |
1308 ms |
124508 KB |
Output is correct |
56 |
Correct |
174 ms |
2068 KB |
Output is correct |
57 |
Correct |
417 ms |
2068 KB |
Output is correct |
58 |
Correct |
606 ms |
3636 KB |
Output is correct |
59 |
Correct |
1635 ms |
117496 KB |
Output is correct |
60 |
Correct |
2180 ms |
117516 KB |
Output is correct |
61 |
Correct |
1575 ms |
117624 KB |
Output is correct |
62 |
Correct |
1330 ms |
129144 KB |
Output is correct |
63 |
Correct |
2021 ms |
125324 KB |
Output is correct |
64 |
Correct |
1624 ms |
119772 KB |
Output is correct |
65 |
Correct |
1416 ms |
117980 KB |
Output is correct |
66 |
Correct |
1707 ms |
118424 KB |
Output is correct |
67 |
Correct |
1633 ms |
127592 KB |
Output is correct |
68 |
Correct |
1449 ms |
150012 KB |
Output is correct |
69 |
Correct |
2210 ms |
168440 KB |
Output is correct |