| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 76323 |
2018-09-12T15:12:07 Z |
kig9981 |
None (KOI18_matrix) |
C++17 |
|
2820 ms |
787456 KB |
#include <bits/stdc++.h>
#ifdef NON_SUBMIT
#define TEST(n) (n)
#else
#define TEST(n) ((void)0)
#endif
using namespace std;
struct Seg2D
{
int xp, yp, xl, xr, yl, yr, v;
Seg2D() : xp(0), yp(0), xl(0), xr(0), yl(0), yr(0), v(0) {}
};
vector<Seg2D> tree(2);
vector<int> X, Y;
vector<tuple<int, int, int>> V;
int mN;
void CreateNode(int n, int b, int p, int s, int e)
{
while (s < e) {
int m = (s + e) >> 1;
if (n <= m) {
if (tree[b].yl == 0) {
tree[b].yl = tree.size();
tree.push_back(Seg2D());
tree[tree[b].yl].yp = b;
}
if (tree[p].yl == 0) {
tree[p].yl = tree.size();
tree.push_back(Seg2D());
tree[tree[p].yl].yp = p;
}
if (tree[b].xl == p) {
tree[tree[b].yl].xl = tree[p].yl;
}
else {
tree[tree[b].yl].xr = tree[p].yl;
}
tree[tree[p].yl].xp = tree[b].yl;
b = tree[b].yl;
p = tree[p].yl;
e = m;
}
else {
if (tree[b].yr == 0) {
tree[b].yr = tree.size();
tree.push_back(Seg2D());
tree[tree[b].yr].yp = b;
}
if (tree[p].yr == 0) {
tree[p].yr = tree.size();
tree.push_back(Seg2D());
tree[tree[p].yr].yp = p;
}
if (tree[b].xl == p) {
tree[tree[b].yr].xl = tree[p].yr;
}
else {
tree[tree[b].yr].xr = tree[p].yr;
}
tree[tree[p].yr].xp = tree[b].yr;
b = tree[b].yr;
p = tree[p].yr;
s = m + 1;
}
}
}
void set_tree(int n1, int n2, int v, int p = 1, int s1 = 1, int e1 = mN, int s2 = 1, int e2 = mN)
{
while (s1 < e1) {
int m1 = (s1 + e1) >> 1;
if (n1 <= m1) {
if (tree[p].xl == 0) {
tree[p].xl = tree.size();
tree.push_back(Seg2D());
tree[tree[p].xl].xp = p;
}
CreateNode(n2, p, tree[p].xl, s2, e2);
p = tree[p].xl;
e1 = m1;
}
else {
if (tree[p].xr == 0) {
tree[p].xr = tree.size();
tree.push_back(Seg2D());
tree[tree[p].xr].xp = p;
}
CreateNode(n2, p, tree[p].xr, s2, e2);
p = tree[p].xr;
s1 = m1 + 1;
}
}
while (s2 < e2) {
int m2 = (s2 + e2) >> 1;
if (n2 <= m2) {
p = tree[p].yl;
e2 = m2;
}
else {
p = tree[p].yr;
s2 = m2 + 1;
}
}
tree[p].v = v;
for (int c = tree[p].yp; c; c = tree[c].yp) {
tree[c].v = max(tree[tree[c].yl].v, tree[tree[c].yr].v);
}
for (int xc = tree[p].xp; xc; xc = tree[xc].xp) {
tree[xc].v = max(tree[tree[xc].xl].v, tree[tree[xc].xr].v);
for (int yc = tree[xc].yp; yc; yc = tree[yc].yp) {
tree[yc].v = max(max(tree[tree[yc].xl].v, tree[tree[yc].xr].v), max(tree[tree[yc].yl].v, tree[tree[yc].yr].v));
}
}
}
int get_max(int x1, int x2, int y1, int y2, int p = 1, int s1 = 1, int e1 = mN, int s2 = 1, int e2 = mN)
{
int m1 = (s1 + e1) >> 1, m2 = (s2 + e2) >> 1;
if (p == 0 || x2 < x1 || x2 < s1 || e1 < x1 || y2 < y1 || y2 < s2 || e2 < y1) {
return 0;
}
if (x1 <= s1 && e1 <= x2) {
if (y1 <= s2 && e2 <= y2) {
return tree[p].v;
}
return max(get_max(x1, x2, y1, y2, tree[p].yl, s1, e1, s2, m2), get_max(x1, x2, y1, y2, tree[p].yr, s1, e1, m2 + 1, e2));
}
return max(get_max(x1, x2, y1, y2, tree[p].xl, s1, m1, s2, e2), get_max(x1, x2, y1, y2, tree[p].xr, m1 + 1, e1, s2, e2));
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
TEST(freopen("input.txt", "r", stdin));
TEST(freopen("output.txt", "w", stdout));
int M, N;
cin >> M >> N;
V.resize(N);
for (mN = 1; mN < N; mN <<= 1);
for (int i = 0; i < N; i++) {
cin >> get<0>(V[i]);
}
for (int i = 0; i < N; i++) {
cin >> get<1>(V[i]);
X.push_back(get<1>(V[i]));
}
sort(X.begin(), X.end());
if (M == 3) {
for (int i = 0; i < N; i++) {
cin >> get<2>(V[i]);
Y.push_back(get<2>(V[i]));
}
sort(V.begin(), V.end());
sort(Y.begin(), Y.end());
}
else {
sort(V.begin(), V.end());
for (int i = 0; i < N; i++) {
Y.push_back(get<2>(V[i]) = i);
}
}
for (auto &[t, x, y] : V) {
x = upper_bound(X.begin(), X.end(), x) - X.begin();
y = upper_bound(Y.begin(), Y.end(), y) - Y.begin();
set_tree(x, y, get_max(1, x - 1, 1, y - 1) + 1);
}
cout << tree[1].v << '\n';
return 0;
}
Compilation message
matrix.cpp: In function 'int main()':
matrix.cpp:168:21: warning: unused variable 't' [-Wunused-variable]
for (auto &[t, x, y] : V) {
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
159 ms |
58588 KB |
Output is correct |
| 2 |
Correct |
104 ms |
58588 KB |
Output is correct |
| 3 |
Correct |
113 ms |
58588 KB |
Output is correct |
| 4 |
Correct |
95 ms |
58588 KB |
Output is correct |
| 5 |
Correct |
150 ms |
59472 KB |
Output is correct |
| 6 |
Correct |
89 ms |
59472 KB |
Output is correct |
| 7 |
Correct |
93 ms |
59472 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
101 ms |
59472 KB |
Output is correct |
| 2 |
Correct |
99 ms |
59472 KB |
Output is correct |
| 3 |
Correct |
139 ms |
59472 KB |
Output is correct |
| 4 |
Correct |
196 ms |
61292 KB |
Output is correct |
| 5 |
Correct |
108 ms |
61292 KB |
Output is correct |
| 6 |
Correct |
91 ms |
61292 KB |
Output is correct |
| 7 |
Correct |
179 ms |
62140 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
159 ms |
58588 KB |
Output is correct |
| 2 |
Correct |
104 ms |
58588 KB |
Output is correct |
| 3 |
Correct |
113 ms |
58588 KB |
Output is correct |
| 4 |
Correct |
95 ms |
58588 KB |
Output is correct |
| 5 |
Correct |
150 ms |
59472 KB |
Output is correct |
| 6 |
Correct |
89 ms |
59472 KB |
Output is correct |
| 7 |
Correct |
93 ms |
59472 KB |
Output is correct |
| 8 |
Runtime error |
2527 ms |
787456 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
101 ms |
59472 KB |
Output is correct |
| 2 |
Correct |
99 ms |
59472 KB |
Output is correct |
| 3 |
Correct |
139 ms |
59472 KB |
Output is correct |
| 4 |
Correct |
196 ms |
61292 KB |
Output is correct |
| 5 |
Correct |
108 ms |
61292 KB |
Output is correct |
| 6 |
Correct |
91 ms |
61292 KB |
Output is correct |
| 7 |
Correct |
179 ms |
62140 KB |
Output is correct |
| 8 |
Runtime error |
2820 ms |
787456 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 9 |
Halted |
0 ms |
0 KB |
- |
