# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
139340 |
2019-07-31T15:00:47 Z |
super_j6 |
Seats (IOI18_seats) |
C++14 |
|
3420 ms |
204668 KB |
#include "seats.h"
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define endl '\n'
struct sq{
int t1 = 0, t3 = 0;
friend bool operator<(sq a, sq b){
return make_pair(a.t1 , a.t3) < make_pair(b.t1, b.t3);
}
friend bool operator==(sq a, sq b){
return make_pair(a.t1 , a.t3) == make_pair(b.t1, b.t3);
}
friend sq operator+(sq a, sq b){
return (sq){a.t1 + b.t1, a.t3 + b.t3};
}
friend sq operator*(int a, sq b){
return (sq){a * b.t1, a * b.t3};
}
};
struct segTree{
int l, r;
segTree *left, *right;
pair<sq, int> val;
sq lazy;
segTree(int a, int b){
l = a;
r = b;
if(l != r){
int mid = (l + r) / 2;
left = new segTree(l, mid);
right = new segTree(mid + 1, r);
val.second = left->val.second + right->val.second;
}else{
val.second = 1;
}
}
void add(int a, int b, sq x){
if(l > b || r < a) return;
if(l >= a && r <= b){
val.first = val.first + x + lazy;
if(l != r){
left->lazy = left->lazy + x + lazy;
right->lazy = right->lazy + x + lazy;
}
lazy = (sq){0, 0};
return;
}
left->lazy = left->lazy + lazy;
right->lazy = right->lazy + lazy;
lazy = (sq){0, 0};
left->add(a, b, x);
right->add(a, b, x);
sq lv = left->val.first + left->lazy, rv = right->val.first + right->lazy;
val.first = min(lv, rv);
val.second = 0;
if(val.first == lv) val.second += left->val.second;
if(val.first == rv) val.second += right->val.second;
}
};
const int maxn = 1000000;
int h, w, n;
bool used[maxn];
int r[maxn], c[maxn];
vector<vector<int>> p;
segTree *tre;
int dx[9] = {0, 1, 1, 0, -1, -1, -1, 0, 1};
int dy[9] = {0, 0, 1, 1, 1, 0, -1, -1, -1};
sq d[5] = {(sq){0, 0}, (sq){1, 0}, (sq){-1, 0}, (sq){0, 1}, (sq){0, -1}};
sq tch(int x, int y, int v){
int ret = 0;
for(int i = 0; i < 4; i++){
ret += (p[x + dx[i]][y + dy[i]] <= v);
}
return d[ret];
}
void chg(int v, int m){
sq s;
for(int i = 0; i < 4; i++){
s = s + tch(r[v] - dx[i], c[v] - dy[i], v);
}
tre->add(v, n - 1, m * s);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C){
h = H + 2, w = W + 2, n = H * W;
p.resize(h);
for(int i = 0; i < h; i++) p[i].resize(w);
tre = new segTree(0, n - 1);
for(int i = 0; i < n; i++){
r[i] = R[i] + 1;
c[i] = C[i] + 1;
p[r[i]][c[i]] = i;
}
for(int i = 0; i < h; i++) p[i][0] = p[i][w - 1] = maxn;
for(int i = 0; i < w; i++) p[0][i] = p[h - 1][i] = maxn;
for(int i = 0; i < n; i++) chg(i, 1);
}
void swp(int v, int m){
for(int i = 0; i < 9; i++){
int nv = p[r[v] + dx[i]][c[v] + dy[i]];
if(nv != maxn && !used[nv]){
chg(nv, m);
used[nv] = 1;
}
}
}
void rst(int v){
for(int i = 0; i < 9; i++){
int nv = p[r[v] + dx[i]][c[v] + dy[i]];
if(nv != maxn) used[nv] = 0;
}
}
int swap_seats(int a, int b){
swp(a, -1), swp(b, -1);
rst(a), rst(b);
swap(c[a], c[b]);
swap(r[a], r[b]);
swap(p[r[a]][c[a]], p[r[b]][c[b]]);
swp(a, 1), swp(b, 1);
rst(a), rst(b);
/*
for(int i = 1; i < h - 1; i++){
for(int j = 1; j < w - 1; j++) cout << p[i][j] << " ";
cout << endl;
}
*/
return tre->val.second;
}
/*
int main(){
int h, w;
cin >> h >> w;
vector<int> a(h * w), b(h * w);
for(int i = 0; i < h * w; i++) cin >> a[i] >> b[i];
give_initial_chart(h, w, a, b);
cout << swap_seats(0, 5) << endl;
cout << swap_seats(0, 5) << endl;
return 0;
}
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
632 KB |
Output is correct |
2 |
Correct |
31 ms |
632 KB |
Output is correct |
3 |
Correct |
40 ms |
504 KB |
Output is correct |
4 |
Correct |
18 ms |
504 KB |
Output is correct |
5 |
Correct |
17 ms |
504 KB |
Output is correct |
6 |
Correct |
31 ms |
504 KB |
Output is correct |
7 |
Correct |
35 ms |
504 KB |
Output is correct |
8 |
Correct |
38 ms |
504 KB |
Output is correct |
9 |
Correct |
38 ms |
504 KB |
Output is correct |
10 |
Correct |
36 ms |
504 KB |
Output is correct |
11 |
Correct |
32 ms |
524 KB |
Output is correct |
12 |
Correct |
18 ms |
508 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
632 KB |
Output is correct |
2 |
Correct |
31 ms |
632 KB |
Output is correct |
3 |
Correct |
40 ms |
504 KB |
Output is correct |
4 |
Correct |
18 ms |
504 KB |
Output is correct |
5 |
Correct |
17 ms |
504 KB |
Output is correct |
6 |
Correct |
31 ms |
504 KB |
Output is correct |
7 |
Correct |
35 ms |
504 KB |
Output is correct |
8 |
Correct |
38 ms |
504 KB |
Output is correct |
9 |
Correct |
38 ms |
504 KB |
Output is correct |
10 |
Correct |
36 ms |
504 KB |
Output is correct |
11 |
Correct |
32 ms |
524 KB |
Output is correct |
12 |
Correct |
18 ms |
508 KB |
Output is correct |
13 |
Correct |
91 ms |
2136 KB |
Output is correct |
14 |
Correct |
103 ms |
2168 KB |
Output is correct |
15 |
Correct |
45 ms |
2172 KB |
Output is correct |
16 |
Correct |
44 ms |
2672 KB |
Output is correct |
17 |
Correct |
65 ms |
2168 KB |
Output is correct |
18 |
Correct |
84 ms |
2168 KB |
Output is correct |
19 |
Correct |
81 ms |
2168 KB |
Output is correct |
20 |
Correct |
62 ms |
2440 KB |
Output is correct |
21 |
Correct |
38 ms |
2168 KB |
Output is correct |
22 |
Correct |
40 ms |
2680 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1403 ms |
154332 KB |
Output is correct |
2 |
Correct |
1185 ms |
153556 KB |
Output is correct |
3 |
Correct |
1164 ms |
153856 KB |
Output is correct |
4 |
Correct |
1163 ms |
153636 KB |
Output is correct |
5 |
Correct |
1148 ms |
153528 KB |
Output is correct |
6 |
Correct |
1123 ms |
153592 KB |
Output is correct |
7 |
Correct |
1151 ms |
153592 KB |
Output is correct |
8 |
Correct |
1191 ms |
153592 KB |
Output is correct |
9 |
Correct |
1159 ms |
153724 KB |
Output is correct |
10 |
Correct |
1160 ms |
153592 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
90 ms |
2196 KB |
Output is correct |
2 |
Correct |
194 ms |
14712 KB |
Output is correct |
3 |
Correct |
1177 ms |
153848 KB |
Output is correct |
4 |
Correct |
1380 ms |
153812 KB |
Output is correct |
5 |
Correct |
1054 ms |
161612 KB |
Output is correct |
6 |
Correct |
1598 ms |
204668 KB |
Output is correct |
7 |
Correct |
1161 ms |
156448 KB |
Output is correct |
8 |
Correct |
1160 ms |
153848 KB |
Output is correct |
9 |
Correct |
1229 ms |
154284 KB |
Output is correct |
10 |
Correct |
1167 ms |
158580 KB |
Output is correct |
11 |
Correct |
1137 ms |
177168 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
52 ms |
1768 KB |
Output is correct |
2 |
Correct |
98 ms |
1868 KB |
Output is correct |
3 |
Correct |
163 ms |
1908 KB |
Output is correct |
4 |
Correct |
221 ms |
2168 KB |
Output is correct |
5 |
Correct |
309 ms |
3604 KB |
Output is correct |
6 |
Correct |
1584 ms |
161912 KB |
Output is correct |
7 |
Correct |
1633 ms |
161644 KB |
Output is correct |
8 |
Correct |
1666 ms |
161840 KB |
Output is correct |
9 |
Correct |
2068 ms |
161920 KB |
Output is correct |
10 |
Correct |
1484 ms |
177824 KB |
Output is correct |
11 |
Correct |
1488 ms |
177776 KB |
Output is correct |
12 |
Correct |
1455 ms |
177816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
632 KB |
Output is correct |
2 |
Correct |
31 ms |
632 KB |
Output is correct |
3 |
Correct |
40 ms |
504 KB |
Output is correct |
4 |
Correct |
18 ms |
504 KB |
Output is correct |
5 |
Correct |
17 ms |
504 KB |
Output is correct |
6 |
Correct |
31 ms |
504 KB |
Output is correct |
7 |
Correct |
35 ms |
504 KB |
Output is correct |
8 |
Correct |
38 ms |
504 KB |
Output is correct |
9 |
Correct |
38 ms |
504 KB |
Output is correct |
10 |
Correct |
36 ms |
504 KB |
Output is correct |
11 |
Correct |
32 ms |
524 KB |
Output is correct |
12 |
Correct |
18 ms |
508 KB |
Output is correct |
13 |
Correct |
91 ms |
2136 KB |
Output is correct |
14 |
Correct |
103 ms |
2168 KB |
Output is correct |
15 |
Correct |
45 ms |
2172 KB |
Output is correct |
16 |
Correct |
44 ms |
2672 KB |
Output is correct |
17 |
Correct |
65 ms |
2168 KB |
Output is correct |
18 |
Correct |
84 ms |
2168 KB |
Output is correct |
19 |
Correct |
81 ms |
2168 KB |
Output is correct |
20 |
Correct |
62 ms |
2440 KB |
Output is correct |
21 |
Correct |
38 ms |
2168 KB |
Output is correct |
22 |
Correct |
40 ms |
2680 KB |
Output is correct |
23 |
Correct |
1403 ms |
154332 KB |
Output is correct |
24 |
Correct |
1185 ms |
153556 KB |
Output is correct |
25 |
Correct |
1164 ms |
153856 KB |
Output is correct |
26 |
Correct |
1163 ms |
153636 KB |
Output is correct |
27 |
Correct |
1148 ms |
153528 KB |
Output is correct |
28 |
Correct |
1123 ms |
153592 KB |
Output is correct |
29 |
Correct |
1151 ms |
153592 KB |
Output is correct |
30 |
Correct |
1191 ms |
153592 KB |
Output is correct |
31 |
Correct |
1159 ms |
153724 KB |
Output is correct |
32 |
Correct |
1160 ms |
153592 KB |
Output is correct |
33 |
Correct |
90 ms |
2196 KB |
Output is correct |
34 |
Correct |
194 ms |
14712 KB |
Output is correct |
35 |
Correct |
1177 ms |
153848 KB |
Output is correct |
36 |
Correct |
1380 ms |
153812 KB |
Output is correct |
37 |
Correct |
1054 ms |
161612 KB |
Output is correct |
38 |
Correct |
1598 ms |
204668 KB |
Output is correct |
39 |
Correct |
1161 ms |
156448 KB |
Output is correct |
40 |
Correct |
1160 ms |
153848 KB |
Output is correct |
41 |
Correct |
1229 ms |
154284 KB |
Output is correct |
42 |
Correct |
1167 ms |
158580 KB |
Output is correct |
43 |
Correct |
1137 ms |
177168 KB |
Output is correct |
44 |
Correct |
52 ms |
1768 KB |
Output is correct |
45 |
Correct |
98 ms |
1868 KB |
Output is correct |
46 |
Correct |
163 ms |
1908 KB |
Output is correct |
47 |
Correct |
221 ms |
2168 KB |
Output is correct |
48 |
Correct |
309 ms |
3604 KB |
Output is correct |
49 |
Correct |
1584 ms |
161912 KB |
Output is correct |
50 |
Correct |
1633 ms |
161644 KB |
Output is correct |
51 |
Correct |
1666 ms |
161840 KB |
Output is correct |
52 |
Correct |
2068 ms |
161920 KB |
Output is correct |
53 |
Correct |
1484 ms |
177824 KB |
Output is correct |
54 |
Correct |
1488 ms |
177776 KB |
Output is correct |
55 |
Correct |
1455 ms |
177816 KB |
Output is correct |
56 |
Correct |
142 ms |
2076 KB |
Output is correct |
57 |
Correct |
369 ms |
2044 KB |
Output is correct |
58 |
Correct |
826 ms |
3696 KB |
Output is correct |
59 |
Correct |
2648 ms |
170012 KB |
Output is correct |
60 |
Correct |
3420 ms |
169972 KB |
Output is correct |
61 |
Correct |
2387 ms |
170024 KB |
Output is correct |
62 |
Correct |
1978 ms |
173960 KB |
Output is correct |
63 |
Correct |
2979 ms |
172536 KB |
Output is correct |
64 |
Correct |
2456 ms |
170912 KB |
Output is correct |
65 |
Correct |
2344 ms |
170104 KB |
Output is correct |
66 |
Correct |
2632 ms |
170408 KB |
Output is correct |
67 |
Correct |
2458 ms |
174596 KB |
Output is correct |
68 |
Correct |
2007 ms |
184420 KB |
Output is correct |
69 |
Correct |
2834 ms |
193400 KB |
Output is correct |