# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
101390 |
2019-03-18T23:18:00 Z |
Noam527 |
Seats (IOI18_seats) |
C++17 |
|
3181 ms |
123272 KB |
#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 1e18;
const int OO = 0;
const int OOO = 0;
using namespace std;
struct segtree {
int n;
vector<int> mn, cnt, tag;
segtree() {}
segtree(const vector<int> &a) {
n = a.size();
while (n != (n & -n)) n += (n & -n);
mn.resize(2 * n, 0);
tag.resize(2 * n, 0);
cnt.resize(2 * n, 1);
for (int i = 0; i < a.size(); i++)
mn[i + n - 1] = a[i];
for (int i = n - 2; i >= 0; i--) fix(i);
}
void push(int x) {
mn[x] += tag[x];
if (x < n - 1) {
tag[2 * x + 1] += tag[x];
tag[2 * x + 2] += tag[x];
}
tag[x] = 0;
}
void fix(int x) {
push(2 * x + 1), push(2 * x + 2);
mn[x] = min(mn[2 * x + 1], mn[2 * x + 2]);
if (mn[2 * x + 1] < mn[2 * x + 2])
cnt[x] = cnt[2 * x + 1];
else if (mn[2 * x + 1] > mn[2 * x + 2])
cnt[x] = cnt[2 * x + 2];
else
cnt[x] = cnt[2 * x + 1] + cnt[2 * x + 2];
}
void upd(int l, int r, int add) {
if (l > r) return;
upd(l, r, add, 0, 0, n - 1);
}
void upd(int l, int r, int add, int node, int nl, int nr) {
if (r < nl || nr < l) return;
if (l <= nl && nr <= r) {
tag[node] += add;
return;
}
push(node);
int mid = (nl + nr) / 2;
upd(l, r, add, 2 * node + 1, nl, mid);
upd(l, r, add, 2 * node + 2, mid + 1, nr);
fix(node);
}
int query(int l, int r) {
return query(l, r, 0, 0, n - 1).second;
}
pair<int, int> query(int l, int r, int node, int nl, int nr) {
if (r < nl || nr < l) return{ md, 0 };
push(node);
if (l <= nl && nr <= r) {
return{ mn[node], cnt[node] };
}
int mid = (nl + nr) / 2;
pair<int, int> p1 = query(l, r, 2 * node + 1, nl, mid);
pair<int, int> p2 = query(l, r, 2 * node + 2, mid + 1, nr);
if (p1.first == p2.first) return{ p1.first, p1.second + p2.second };
return min(p1, p2);
}
void print() {
for (int i = 0; i < 2 * n - 1; i++) push(i);
for (int i = n - 1; i < 2 * n - 1; i++) cout << mn[i] << " "; cout << '\n';
}
};
int n, m, en;
vector<int> r, c;
vector<vector<int>> A;
segtree S;
vector<int> pre;
void upd(int i, int j, int add) {
static const int dx[4] = { 0,-1,0,-1 };
static const int dy[4] = { 0,0,-1,-1 };
vector<int> T;
for (int k = 0; k < 4; k++)
if (0 <= i + dx[k] && i + dx[k] < n && 0 <= j + dy[k] && j + dy[k] < m)
T.push_back(A[i + dx[k]][j + dy[k]]);
sort(T.begin(), T.end());
if (T.size() & 1) T.push_back(en);
for (int k = 0; k < T.size(); k += 2) {
if (OO) {
cout << "cell (" << i << ", " << j << ") adds range [" << T[k] << ", " << T[k + 1] - 1 << "]\n";
}
S.upd(T[k], T[k + 1] - 1, add);
}
}
void slowupd(int i, int j, int add) {
static const int dx[4] = { 0,-1,0,-1 };
static const int dy[4] = { 0,0,-1,-1 };
vector<int> T;
for (int k = 0; k < 4; k++)
if (0 <= i + dx[k] && i + dx[k] < n && 0 <= j + dy[k] && j + dy[k] < m)
T.push_back(A[i + dx[k]][j + dy[k]]);
sort(T.begin(), T.end());
if (T.size() & 1) T.push_back(en);
for (int k = 0; k < T.size(); k += 2) {
if (OO) {
cout << "cell (" << i << ", " << j << ") adds range [" << T[k] << ", " << T[k + 1] - 1 << "]\n";
}
pre[T[k]] += add;
if (T[k + 1] < en) pre[T[k + 1]] -= add;
}
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
n = H;
m = W;
en = n * m;
r = R;
c = C;
A.resize(n, vector<int>(m));
for (int i = 0; i < n * m; i++)
A[r[i]][c[i]] = i;
pre.resize(n * m, 0);
for (int i = 0; i <= n; i++) for (int j = 0; j <= m; j++)
slowupd(i, j, 1);
for (int i = 1; i < en; i++) pre[i] += pre[i - 1];
S = segtree(pre);
if (OO) {
cout << "the tree\n";
S.print();
}
}
int swap_seats(int a, int b) {
upd(r[a], c[a], -1);
upd(r[a], c[a] + 1, -1);
upd(r[a] + 1, c[a], -1);
upd(r[a] + 1, c[a] + 1, -1);
upd(r[b], c[b], -1);
upd(r[b], c[b] + 1, -1);
upd(r[b] + 1, c[b], -1);
upd(r[b] + 1, c[b] + 1, -1);
swap(A[r[a]][c[a]], A[r[b]][c[b]]);
swap(r[a], r[b]), swap(c[a], c[b]);
upd(r[a], c[a], 1);
upd(r[a], c[a] + 1, 1);
upd(r[a] + 1, c[a], 1);
upd(r[a] + 1, c[a] + 1, 1);
upd(r[b], c[b], 1);
upd(r[b], c[b] + 1, 1);
upd(r[b] + 1, c[b], 1);
upd(r[b] + 1, c[b] + 1, 1);
if (OO) {
cout << "the tree\n";
S.print();
}
return S.query(0, n * m - 1);
}
/*
int main() {
int nn, mm, qq;
cin >> nn >> mm >> qq;
vector<int> rr(nn*mm), cc(nn*mm);
for (auto &i : rr) cin >> i;
for (auto &i : cc) cin >> i;
give_initial_chart(nn, mm, rr, cc);
while (qq--) {
int a, b;
cin >> a >> b;
cout << swap_seats(a, b) << '\n';
}
}
*/
Compilation message
seats.cpp: In constructor 'segtree::segtree(const std::vector<int>&)':
seats.cpp:22:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a.size(); i++)
~~^~~~~~~~~~
seats.cpp: In member function 'void segtree::print()':
seats.cpp:77:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for (int i = n - 1; i < 2 * n - 1; i++) cout << mn[i] << " "; cout << '\n';
^~~
seats.cpp:77:65: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for (int i = n - 1; i < 2 * n - 1; i++) cout << mn[i] << " "; cout << '\n';
^~~~
seats.cpp: In function 'void upd(int, int, int)':
seats.cpp:96:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int k = 0; k < T.size(); k += 2) {
~~^~~~~~~~~~
seats.cpp: In function 'void slowupd(int, int, int)':
seats.cpp:112:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int k = 0; k < T.size(); k += 2) {
~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
504 KB |
Output is correct |
2 |
Correct |
47 ms |
508 KB |
Output is correct |
3 |
Correct |
53 ms |
504 KB |
Output is correct |
4 |
Correct |
31 ms |
504 KB |
Output is correct |
5 |
Correct |
31 ms |
512 KB |
Output is correct |
6 |
Correct |
58 ms |
504 KB |
Output is correct |
7 |
Correct |
48 ms |
504 KB |
Output is correct |
8 |
Correct |
44 ms |
504 KB |
Output is correct |
9 |
Correct |
42 ms |
504 KB |
Output is correct |
10 |
Correct |
48 ms |
596 KB |
Output is correct |
11 |
Correct |
42 ms |
576 KB |
Output is correct |
12 |
Correct |
37 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
504 KB |
Output is correct |
2 |
Correct |
47 ms |
508 KB |
Output is correct |
3 |
Correct |
53 ms |
504 KB |
Output is correct |
4 |
Correct |
31 ms |
504 KB |
Output is correct |
5 |
Correct |
31 ms |
512 KB |
Output is correct |
6 |
Correct |
58 ms |
504 KB |
Output is correct |
7 |
Correct |
48 ms |
504 KB |
Output is correct |
8 |
Correct |
44 ms |
504 KB |
Output is correct |
9 |
Correct |
42 ms |
504 KB |
Output is correct |
10 |
Correct |
48 ms |
596 KB |
Output is correct |
11 |
Correct |
42 ms |
576 KB |
Output is correct |
12 |
Correct |
37 ms |
504 KB |
Output is correct |
13 |
Correct |
116 ms |
1336 KB |
Output is correct |
14 |
Correct |
125 ms |
1372 KB |
Output is correct |
15 |
Correct |
64 ms |
1400 KB |
Output is correct |
16 |
Correct |
54 ms |
1796 KB |
Output is correct |
17 |
Correct |
118 ms |
1280 KB |
Output is correct |
18 |
Correct |
89 ms |
1280 KB |
Output is correct |
19 |
Correct |
78 ms |
1360 KB |
Output is correct |
20 |
Correct |
80 ms |
1568 KB |
Output is correct |
21 |
Correct |
56 ms |
1280 KB |
Output is correct |
22 |
Correct |
71 ms |
1912 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
946 ms |
56796 KB |
Output is correct |
2 |
Correct |
638 ms |
72440 KB |
Output is correct |
3 |
Correct |
675 ms |
72456 KB |
Output is correct |
4 |
Correct |
712 ms |
72368 KB |
Output is correct |
5 |
Correct |
746 ms |
72452 KB |
Output is correct |
6 |
Correct |
748 ms |
72288 KB |
Output is correct |
7 |
Correct |
757 ms |
72584 KB |
Output is correct |
8 |
Correct |
723 ms |
72312 KB |
Output is correct |
9 |
Correct |
635 ms |
72472 KB |
Output is correct |
10 |
Correct |
642 ms |
72480 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
116 ms |
1312 KB |
Output is correct |
2 |
Correct |
189 ms |
6620 KB |
Output is correct |
3 |
Correct |
566 ms |
56844 KB |
Output is correct |
4 |
Correct |
802 ms |
56824 KB |
Output is correct |
5 |
Correct |
600 ms |
72644 KB |
Output is correct |
6 |
Correct |
1020 ms |
123272 KB |
Output is correct |
7 |
Correct |
619 ms |
72416 KB |
Output is correct |
8 |
Correct |
614 ms |
72444 KB |
Output is correct |
9 |
Correct |
614 ms |
72820 KB |
Output is correct |
10 |
Correct |
742 ms |
75504 KB |
Output is correct |
11 |
Correct |
773 ms |
96008 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
132 ms |
2076 KB |
Output is correct |
2 |
Correct |
248 ms |
2188 KB |
Output is correct |
3 |
Correct |
252 ms |
2052 KB |
Output is correct |
4 |
Correct |
355 ms |
2236 KB |
Output is correct |
5 |
Correct |
705 ms |
2996 KB |
Output is correct |
6 |
Correct |
1381 ms |
56828 KB |
Output is correct |
7 |
Correct |
1512 ms |
56800 KB |
Output is correct |
8 |
Correct |
1460 ms |
56792 KB |
Output is correct |
9 |
Correct |
2031 ms |
56788 KB |
Output is correct |
10 |
Correct |
1444 ms |
73408 KB |
Output is correct |
11 |
Correct |
1274 ms |
73364 KB |
Output is correct |
12 |
Correct |
1343 ms |
73428 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
504 KB |
Output is correct |
2 |
Correct |
47 ms |
508 KB |
Output is correct |
3 |
Correct |
53 ms |
504 KB |
Output is correct |
4 |
Correct |
31 ms |
504 KB |
Output is correct |
5 |
Correct |
31 ms |
512 KB |
Output is correct |
6 |
Correct |
58 ms |
504 KB |
Output is correct |
7 |
Correct |
48 ms |
504 KB |
Output is correct |
8 |
Correct |
44 ms |
504 KB |
Output is correct |
9 |
Correct |
42 ms |
504 KB |
Output is correct |
10 |
Correct |
48 ms |
596 KB |
Output is correct |
11 |
Correct |
42 ms |
576 KB |
Output is correct |
12 |
Correct |
37 ms |
504 KB |
Output is correct |
13 |
Correct |
116 ms |
1336 KB |
Output is correct |
14 |
Correct |
125 ms |
1372 KB |
Output is correct |
15 |
Correct |
64 ms |
1400 KB |
Output is correct |
16 |
Correct |
54 ms |
1796 KB |
Output is correct |
17 |
Correct |
118 ms |
1280 KB |
Output is correct |
18 |
Correct |
89 ms |
1280 KB |
Output is correct |
19 |
Correct |
78 ms |
1360 KB |
Output is correct |
20 |
Correct |
80 ms |
1568 KB |
Output is correct |
21 |
Correct |
56 ms |
1280 KB |
Output is correct |
22 |
Correct |
71 ms |
1912 KB |
Output is correct |
23 |
Correct |
946 ms |
56796 KB |
Output is correct |
24 |
Correct |
638 ms |
72440 KB |
Output is correct |
25 |
Correct |
675 ms |
72456 KB |
Output is correct |
26 |
Correct |
712 ms |
72368 KB |
Output is correct |
27 |
Correct |
746 ms |
72452 KB |
Output is correct |
28 |
Correct |
748 ms |
72288 KB |
Output is correct |
29 |
Correct |
757 ms |
72584 KB |
Output is correct |
30 |
Correct |
723 ms |
72312 KB |
Output is correct |
31 |
Correct |
635 ms |
72472 KB |
Output is correct |
32 |
Correct |
642 ms |
72480 KB |
Output is correct |
33 |
Correct |
116 ms |
1312 KB |
Output is correct |
34 |
Correct |
189 ms |
6620 KB |
Output is correct |
35 |
Correct |
566 ms |
56844 KB |
Output is correct |
36 |
Correct |
802 ms |
56824 KB |
Output is correct |
37 |
Correct |
600 ms |
72644 KB |
Output is correct |
38 |
Correct |
1020 ms |
123272 KB |
Output is correct |
39 |
Correct |
619 ms |
72416 KB |
Output is correct |
40 |
Correct |
614 ms |
72444 KB |
Output is correct |
41 |
Correct |
614 ms |
72820 KB |
Output is correct |
42 |
Correct |
742 ms |
75504 KB |
Output is correct |
43 |
Correct |
773 ms |
96008 KB |
Output is correct |
44 |
Correct |
132 ms |
2076 KB |
Output is correct |
45 |
Correct |
248 ms |
2188 KB |
Output is correct |
46 |
Correct |
252 ms |
2052 KB |
Output is correct |
47 |
Correct |
355 ms |
2236 KB |
Output is correct |
48 |
Correct |
705 ms |
2996 KB |
Output is correct |
49 |
Correct |
1381 ms |
56828 KB |
Output is correct |
50 |
Correct |
1512 ms |
56800 KB |
Output is correct |
51 |
Correct |
1460 ms |
56792 KB |
Output is correct |
52 |
Correct |
2031 ms |
56788 KB |
Output is correct |
53 |
Correct |
1444 ms |
73408 KB |
Output is correct |
54 |
Correct |
1274 ms |
73364 KB |
Output is correct |
55 |
Correct |
1343 ms |
73428 KB |
Output is correct |
56 |
Correct |
307 ms |
2164 KB |
Output is correct |
57 |
Correct |
608 ms |
2220 KB |
Output is correct |
58 |
Correct |
824 ms |
3008 KB |
Output is correct |
59 |
Correct |
2163 ms |
73488 KB |
Output is correct |
60 |
Correct |
3181 ms |
73464 KB |
Output is correct |
61 |
Correct |
1899 ms |
73512 KB |
Output is correct |
62 |
Correct |
1568 ms |
73300 KB |
Output is correct |
63 |
Correct |
2808 ms |
73340 KB |
Output is correct |
64 |
Correct |
2004 ms |
73344 KB |
Output is correct |
65 |
Correct |
1845 ms |
73592 KB |
Output is correct |
66 |
Correct |
2116 ms |
73720 KB |
Output is correct |
67 |
Correct |
2153 ms |
76552 KB |
Output is correct |
68 |
Correct |
1788 ms |
87700 KB |
Output is correct |
69 |
Correct |
2793 ms |
96752 KB |
Output is correct |