# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
118372 |
2019-06-18T20:08:10 Z |
joseacaz |
Seats (IOI18_seats) |
C++17 |
|
3818 ms |
95512 KB |
#include "seats.h"
#include <bits/stdc++.h>
#define MAXN 1000005
#define INF (1 << 30)
#define VARS int mid = (l + r) / 2, lchild = (2 * node) + 1, rchild = (2 * node) + 2
using namespace std;
struct Node
{
int minim, freq;
Node operator + ( const Node& _x ) const
{
Node aux;
if ( minim < _x.minim )
aux.minim = minim, aux.freq = freq;
else if ( minim > _x.minim )
aux.minim = _x.minim, aux.freq = _x.freq;
else
aux.minim = minim, aux.freq = freq + _x.freq;
return aux;
}
void out ()
{
cout << minim << " " << freq << "\n";
}
};
int N, H, W;
vector <int> R, C, A;
vector <vector <int>> seats;
Node ST[4 * MAXN], DEFAULT;
int lazy[4 * MAXN];
void propagate ( int node, int l, int r )
{
ST[node].minim += lazy[node];
if ( l != r )
{
VARS;
lazy[lchild] += lazy[node];
lazy[rchild] += lazy[node];
}
lazy[node] = 0;
}
void build ( int node = 0, int l = 0, int r = N - 1 )
{
if ( l == r )
{
ST[node].minim = 0;
ST[node].freq = 1;
return;
}
VARS;
build ( lchild, l, mid );
build ( rchild, mid + 1, r );
ST[node] = ST[lchild] + ST[rchild];
}
void upd ( int L, int R, int x, int node = 0, int l = 0, int r = N - 1 )
{
propagate ( node, l, r );
if ( r < L or R < l )
return;
if ( L <= l && r <= R )
{
lazy[node] = x;
propagate ( node, l, r );
return;
}
VARS;
upd ( L, R, x, lchild, l, mid );
upd ( L, R, x, rchild, mid + 1, r );
ST[node] = ST[lchild] + ST[rchild];
}
Node qry ( int L, int R, int node = 0, int l = 0, int r = N - 1 )
{
propagate ( node, l, r );
if ( r < L or R < l )
return DEFAULT;
if ( L <= l && r <= R )
return ST[node];
VARS;
return qry ( L, R, lchild, l, mid ) + qry ( L, R, rchild, mid + 1, r );
}
void give_initial_chart ( int _h, int _w, vector <int> _r, vector <int> _c )
{
DEFAULT.minim = INF;
DEFAULT.freq = 0;
H = _h;
W = _w;
N = H * W;
swap ( R, _r );
swap ( C, _c );
seats.resize ( H + 5 );
for ( int i = 0; i < H + 5; i++ )
seats[i].resize ( W + 5 );
for ( int i = 0; i <= W + 1; i++ )
seats[0][i] = N, seats[H + 1][i] = N;
for ( int i = 0; i <= H + 1; i++ )
seats[i][0] = N, seats[i][W + 1] = N;
for ( int i = 0; i < N; i++ )
seats[R[i] + 1][C[i] + 1] = i;
build ( );
for ( int i = 0; i <= H; i++ )
{
for ( int j = 0; j <= W; j++ )
{
A.clear();
A.push_back ( seats[i][j] );
A.push_back ( seats[i][j + 1] );
A.push_back ( seats[i + 1][j] );
A.push_back ( seats[i + 1][j + 1] );
sort ( A.begin(), A.end() );
upd ( A[0], A[1] - 1, 1 );
upd ( A[2], A[3] - 1, 1 );
}
}
}
int swap_seats ( int a, int b )
{
for ( int i = R[a]; i <= R[a] + 1; i++ )
{
for ( int j = C[a]; j <= C[a] + 1; j++ )
{
A.clear();
A.push_back ( seats[i][j] );
A.push_back ( seats[i][j + 1] );
A.push_back ( seats[i + 1][j] );
A.push_back ( seats[i + 1][j + 1] );
sort ( A.begin(), A.end() );
upd ( A[0], A[1] - 1, -1 );
upd ( A[2], A[3] - 1, -1 );
}
}
for ( int i = R[b]; i <= R[b] + 1; i++ )
{
for ( int j = C[b]; j <= C[b] + 1; j++ )
{
A.clear();
A.push_back ( seats[i][j] );
A.push_back ( seats[i][j + 1] );
A.push_back ( seats[i + 1][j] );
A.push_back ( seats[i + 1][j + 1] );
sort ( A.begin(), A.end() );
upd ( A[0], A[1] - 1, -1 );
upd ( A[2], A[3] - 1, -1 );
}
}
swap ( seats[R[a] + 1][C[a] + 1], seats[R[b] + 1][C[b] + 1] );
swap ( R[a], R[b] );
swap ( C[a], C[b] );
for ( int i = R[a]; i <= R[a] + 1; i++ )
{
for ( int j = C[a]; j <= C[a] + 1; j++ )
{
A.clear();
A.push_back ( seats[i][j] );
A.push_back ( seats[i][j + 1] );
A.push_back ( seats[i + 1][j] );
A.push_back ( seats[i + 1][j + 1] );
sort ( A.begin(), A.end() );
upd ( A[0], A[1] - 1, 1 );
upd ( A[2], A[3] - 1, 1 );
}
}
for ( int i = R[b]; i <= R[b] + 1; i++ )
{
for ( int j = C[b]; j <= C[b] + 1; j++ )
{
A.clear();
A.push_back ( seats[i][j] );
A.push_back ( seats[i][j + 1] );
A.push_back ( seats[i + 1][j] );
A.push_back ( seats[i + 1][j + 1] );
sort ( A.begin(), A.end() );
upd ( A[0], A[1] - 1, 1 );
upd ( A[2], A[3] - 1, 1 );
}
}
propagate ( 0, 0, N - 1 );
if ( ST[0].minim == 4 )
return ST[0].freq;
return 0;
}
Compilation message
seats.cpp: In function 'void propagate(int, int, int)':
seats.cpp:5:18: warning: unused variable 'mid' [-Wunused-variable]
#define VARS int mid = (l + r) / 2, lchild = (2 * node) + 1, rchild = (2 * node) + 2
^
seats.cpp:43:3: note: in expansion of macro 'VARS'
VARS;
^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
384 KB |
Output is correct |
2 |
Correct |
24 ms |
504 KB |
Output is correct |
3 |
Correct |
36 ms |
384 KB |
Output is correct |
4 |
Correct |
22 ms |
504 KB |
Output is correct |
5 |
Correct |
20 ms |
384 KB |
Output is correct |
6 |
Correct |
30 ms |
384 KB |
Output is correct |
7 |
Correct |
32 ms |
384 KB |
Output is correct |
8 |
Correct |
31 ms |
604 KB |
Output is correct |
9 |
Correct |
30 ms |
480 KB |
Output is correct |
10 |
Correct |
32 ms |
504 KB |
Output is correct |
11 |
Correct |
31 ms |
424 KB |
Output is correct |
12 |
Correct |
20 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
384 KB |
Output is correct |
2 |
Correct |
24 ms |
504 KB |
Output is correct |
3 |
Correct |
36 ms |
384 KB |
Output is correct |
4 |
Correct |
22 ms |
504 KB |
Output is correct |
5 |
Correct |
20 ms |
384 KB |
Output is correct |
6 |
Correct |
30 ms |
384 KB |
Output is correct |
7 |
Correct |
32 ms |
384 KB |
Output is correct |
8 |
Correct |
31 ms |
604 KB |
Output is correct |
9 |
Correct |
30 ms |
480 KB |
Output is correct |
10 |
Correct |
32 ms |
504 KB |
Output is correct |
11 |
Correct |
31 ms |
424 KB |
Output is correct |
12 |
Correct |
20 ms |
512 KB |
Output is correct |
13 |
Correct |
75 ms |
1144 KB |
Output is correct |
14 |
Correct |
89 ms |
1028 KB |
Output is correct |
15 |
Correct |
52 ms |
1152 KB |
Output is correct |
16 |
Correct |
38 ms |
1528 KB |
Output is correct |
17 |
Correct |
66 ms |
1096 KB |
Output is correct |
18 |
Correct |
62 ms |
1024 KB |
Output is correct |
19 |
Correct |
59 ms |
1172 KB |
Output is correct |
20 |
Correct |
50 ms |
1400 KB |
Output is correct |
21 |
Correct |
39 ms |
1272 KB |
Output is correct |
22 |
Correct |
40 ms |
1536 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2371 ms |
44720 KB |
Output is correct |
2 |
Correct |
1207 ms |
44796 KB |
Output is correct |
3 |
Correct |
1159 ms |
44872 KB |
Output is correct |
4 |
Correct |
992 ms |
44824 KB |
Output is correct |
5 |
Correct |
1065 ms |
44792 KB |
Output is correct |
6 |
Correct |
984 ms |
44792 KB |
Output is correct |
7 |
Correct |
1065 ms |
44884 KB |
Output is correct |
8 |
Correct |
1145 ms |
44920 KB |
Output is correct |
9 |
Correct |
1160 ms |
44812 KB |
Output is correct |
10 |
Correct |
1105 ms |
44964 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
74 ms |
1024 KB |
Output is correct |
2 |
Correct |
177 ms |
5280 KB |
Output is correct |
3 |
Correct |
1037 ms |
44888 KB |
Output is correct |
4 |
Correct |
2398 ms |
44920 KB |
Output is correct |
5 |
Correct |
952 ms |
64412 KB |
Output is correct |
6 |
Correct |
2429 ms |
95512 KB |
Output is correct |
7 |
Correct |
1018 ms |
51288 KB |
Output is correct |
8 |
Correct |
1307 ms |
44960 KB |
Output is correct |
9 |
Correct |
1115 ms |
45328 KB |
Output is correct |
10 |
Correct |
1102 ms |
51176 KB |
Output is correct |
11 |
Correct |
1057 ms |
76124 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
62 ms |
1396 KB |
Output is correct |
2 |
Correct |
119 ms |
1464 KB |
Output is correct |
3 |
Correct |
184 ms |
1540 KB |
Output is correct |
4 |
Correct |
241 ms |
1420 KB |
Output is correct |
5 |
Correct |
386 ms |
2184 KB |
Output is correct |
6 |
Correct |
1522 ms |
65176 KB |
Output is correct |
7 |
Correct |
1855 ms |
65396 KB |
Output is correct |
8 |
Correct |
1474 ms |
65312 KB |
Output is correct |
9 |
Correct |
3145 ms |
65256 KB |
Output is correct |
10 |
Correct |
1421 ms |
65236 KB |
Output is correct |
11 |
Correct |
1463 ms |
81792 KB |
Output is correct |
12 |
Correct |
1379 ms |
81860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
384 KB |
Output is correct |
2 |
Correct |
24 ms |
504 KB |
Output is correct |
3 |
Correct |
36 ms |
384 KB |
Output is correct |
4 |
Correct |
22 ms |
504 KB |
Output is correct |
5 |
Correct |
20 ms |
384 KB |
Output is correct |
6 |
Correct |
30 ms |
384 KB |
Output is correct |
7 |
Correct |
32 ms |
384 KB |
Output is correct |
8 |
Correct |
31 ms |
604 KB |
Output is correct |
9 |
Correct |
30 ms |
480 KB |
Output is correct |
10 |
Correct |
32 ms |
504 KB |
Output is correct |
11 |
Correct |
31 ms |
424 KB |
Output is correct |
12 |
Correct |
20 ms |
512 KB |
Output is correct |
13 |
Correct |
75 ms |
1144 KB |
Output is correct |
14 |
Correct |
89 ms |
1028 KB |
Output is correct |
15 |
Correct |
52 ms |
1152 KB |
Output is correct |
16 |
Correct |
38 ms |
1528 KB |
Output is correct |
17 |
Correct |
66 ms |
1096 KB |
Output is correct |
18 |
Correct |
62 ms |
1024 KB |
Output is correct |
19 |
Correct |
59 ms |
1172 KB |
Output is correct |
20 |
Correct |
50 ms |
1400 KB |
Output is correct |
21 |
Correct |
39 ms |
1272 KB |
Output is correct |
22 |
Correct |
40 ms |
1536 KB |
Output is correct |
23 |
Correct |
2371 ms |
44720 KB |
Output is correct |
24 |
Correct |
1207 ms |
44796 KB |
Output is correct |
25 |
Correct |
1159 ms |
44872 KB |
Output is correct |
26 |
Correct |
992 ms |
44824 KB |
Output is correct |
27 |
Correct |
1065 ms |
44792 KB |
Output is correct |
28 |
Correct |
984 ms |
44792 KB |
Output is correct |
29 |
Correct |
1065 ms |
44884 KB |
Output is correct |
30 |
Correct |
1145 ms |
44920 KB |
Output is correct |
31 |
Correct |
1160 ms |
44812 KB |
Output is correct |
32 |
Correct |
1105 ms |
44964 KB |
Output is correct |
33 |
Correct |
74 ms |
1024 KB |
Output is correct |
34 |
Correct |
177 ms |
5280 KB |
Output is correct |
35 |
Correct |
1037 ms |
44888 KB |
Output is correct |
36 |
Correct |
2398 ms |
44920 KB |
Output is correct |
37 |
Correct |
952 ms |
64412 KB |
Output is correct |
38 |
Correct |
2429 ms |
95512 KB |
Output is correct |
39 |
Correct |
1018 ms |
51288 KB |
Output is correct |
40 |
Correct |
1307 ms |
44960 KB |
Output is correct |
41 |
Correct |
1115 ms |
45328 KB |
Output is correct |
42 |
Correct |
1102 ms |
51176 KB |
Output is correct |
43 |
Correct |
1057 ms |
76124 KB |
Output is correct |
44 |
Correct |
62 ms |
1396 KB |
Output is correct |
45 |
Correct |
119 ms |
1464 KB |
Output is correct |
46 |
Correct |
184 ms |
1540 KB |
Output is correct |
47 |
Correct |
241 ms |
1420 KB |
Output is correct |
48 |
Correct |
386 ms |
2184 KB |
Output is correct |
49 |
Correct |
1522 ms |
65176 KB |
Output is correct |
50 |
Correct |
1855 ms |
65396 KB |
Output is correct |
51 |
Correct |
1474 ms |
65312 KB |
Output is correct |
52 |
Correct |
3145 ms |
65256 KB |
Output is correct |
53 |
Correct |
1421 ms |
65236 KB |
Output is correct |
54 |
Correct |
1463 ms |
81792 KB |
Output is correct |
55 |
Correct |
1379 ms |
81860 KB |
Output is correct |
56 |
Correct |
147 ms |
2024 KB |
Output is correct |
57 |
Correct |
337 ms |
2116 KB |
Output is correct |
58 |
Correct |
566 ms |
2988 KB |
Output is correct |
59 |
Correct |
2061 ms |
62364 KB |
Output is correct |
60 |
Correct |
3769 ms |
62436 KB |
Output is correct |
61 |
Correct |
1893 ms |
62652 KB |
Output is correct |
62 |
Correct |
1565 ms |
72076 KB |
Output is correct |
63 |
Correct |
3818 ms |
68980 KB |
Output is correct |
64 |
Correct |
2280 ms |
64368 KB |
Output is correct |
65 |
Correct |
2151 ms |
62480 KB |
Output is correct |
66 |
Correct |
2131 ms |
63040 KB |
Output is correct |
67 |
Correct |
2236 ms |
68764 KB |
Output is correct |
68 |
Correct |
1654 ms |
81900 KB |
Output is correct |
69 |
Correct |
3435 ms |
93536 KB |
Output is correct |