| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 361609 |
2021-01-30T19:36:58 Z |
gratus907 |
None (KOI18_matrix) |
C++17 |
|
132 ms |
31804 KB |
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define ll long long
#define eps 1e-7
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
using pii = pair<int, int>;
void solve_2();
int m, n;
int arr[3][202020];
set <int> s;
const int MAXR = 1000000007;
const int MAXC = 1000000007;
// max-dynamic-2seg
// msg555 impl, some modifications
int agg(int a, int b) {return max(a, b);}
struct Dynamic2DSeg
{
struct Node
{
Node (int l, int r, int v = 0) : l(l), r(r), v(v), lc(NULL), rc(NULL){}
int l, r, v;
Node *lc, *rc;
};
struct RowNode
{
RowNode () : lc(NULL), rc(NULL), rowRoot(0, MAXC){}
Node rowRoot;
RowNode *lc, *rc;
};
RowNode root;
static void update2(Node *node, int idx, int dt)
{
int lo = node -> l;
int hi = node -> r;
int mid = (lo + hi) / 2;
if (lo + 1 == hi)
{
node -> v = dt;
return;
}
Node *& next = idx < mid ? node -> lc : node -> rc;
if (next == NULL)
next = new Node(idx, idx + 1, dt);
else if (next -> l <= idx && idx <= next -> r)
update2(next, idx, dt);
else
{
do {
(idx < mid ? hi : lo) = mid;
mid = (lo + hi) / 2;
} while ((idx < mid) == (next->l < mid));
Node * nnode = new Node(lo, hi);
next->l < mid ? nnode->lc : nnode->rc = next;
next = nnode;
update2(nnode, idx, dt);
}
node -> v = agg(node->lc?node->lc->v:0, node->rc?node->rc->v:0);
}
static void update1(RowNode * node, int lo, int hi, int ridx, int idx, int dt)
{
int mid = (lo + hi) / 2;
if (lo + 1 == hi)
update2(&node -> rowRoot, idx, dt);
else
{
RowNode *& nnode = ridx < mid ? node -> lc : node -> rc;
(ridx < mid ? hi : lo) = mid;
if (nnode == NULL)
nnode = new RowNode();
update1(nnode, lo, hi, ridx, idx, dt);
update2(&node->rowRoot, idx, dt);
}
}
static int query2(Node *node, int a, int b)
{
if (node == NULL || b <= node -> l || node -> r <= a)
return 0;
else if (a <= node -> l && node -> r <= b)
return node -> v;
return agg(query2(node->lc, a, b), query2(node->rc, a, b));
}
static int query1(RowNode *node, int lo, int hi, int a1, int b1, int a2, int b2)
{
if (node == NULL || b1 <= lo || hi <= a1)
return 0;
else if (a1 <= lo && hi <= b1)
return query2(&node->rowRoot, a2, b2);
int mid = (lo + hi) / 2;
return agg(query1(node->lc, lo, mid, a1, b1, a2, b2),
query1(node->rc, mid, hi, a1, b1, a2, b2));
}
void update(int x, int y, int dt)
{
update1(&root, 0, MAXR, x, y, dt);
}
int query(int x1, int y1, int x2, int y2)
{
return query1(&root, 0, MAXR, x1, x2 + 1, y1, y2 + 1);
}
} DSEG;
void solve_3()
{
vector <pair<int, pii>> v;
for (int i = 0; i < n; i++)
v.push_back({arr[0][i], {arr[1][i], arr[2][i]}});
sort(all(v));
vector <int> ans(n, 0);
for (int i = n; i >= 0; i--)
{
int cx = v[i].second.first;
int cy = v[i].second.second;
ans[i] = DSEG.query(cx+1, cy+1, 1e9+1, 1e9+1) + 1;
DSEG.update(cx, cy, ans[i]);
}
int r = 0;
for (auto it:ans)
r = max(it, r);
cout << r << '\n';
}
int32_t main()
{
usecppio
cin >> m >> n;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
cin >> arr[i][j];
if (m == 2)
solve_2();
else solve_3();
}
void solve_2()
{
vector <pii> v;
for (int i = 0; i < n; i++)
v.push_back({arr[0][i], arr[1][i]});
sort(all(v));
vector <int> vv;
for (int i = 0; i < n; i++)
vv.push_back(v[i].second);
set <int> :: iterator it;
for (int i = 0; i < n; i++)
{
s.insert(vv[i]);
it = s.upper_bound(vv[i]);
if (it != s.end())
s.erase(it);
}
cout << s.size() << '\n';
}
Compilation message
matrix.cpp: In constructor 'Dynamic2DSeg::RowNode::RowNode()':
matrix.cpp:33:23: warning: 'Dynamic2DSeg::RowNode::rc' will be initialized after [-Wreorder]
33 | RowNode *lc, *rc;
| ^~
matrix.cpp:32:14: warning: 'Dynamic2DSeg::Node Dynamic2DSeg::RowNode::rowRoot' [-Wreorder]
32 | Node rowRoot;
| ^~~~~~~
matrix.cpp:31:9: warning: when initialized here [-Wreorder]
31 | RowNode () : lc(NULL), rc(NULL), rowRoot(0, MAXC){}
| ^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
620 KB |
Output is correct |
| 2 |
Correct |
5 ms |
620 KB |
Output is correct |
| 3 |
Correct |
5 ms |
620 KB |
Output is correct |
| 4 |
Correct |
5 ms |
748 KB |
Output is correct |
| 5 |
Correct |
5 ms |
620 KB |
Output is correct |
| 6 |
Correct |
5 ms |
1004 KB |
Output is correct |
| 7 |
Correct |
5 ms |
748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
74 ms |
31804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
620 KB |
Output is correct |
| 2 |
Correct |
5 ms |
620 KB |
Output is correct |
| 3 |
Correct |
5 ms |
620 KB |
Output is correct |
| 4 |
Correct |
5 ms |
748 KB |
Output is correct |
| 5 |
Correct |
5 ms |
620 KB |
Output is correct |
| 6 |
Correct |
5 ms |
1004 KB |
Output is correct |
| 7 |
Correct |
5 ms |
748 KB |
Output is correct |
| 8 |
Correct |
104 ms |
5356 KB |
Output is correct |
| 9 |
Correct |
103 ms |
5348 KB |
Output is correct |
| 10 |
Correct |
101 ms |
6500 KB |
Output is correct |
| 11 |
Correct |
88 ms |
5348 KB |
Output is correct |
| 12 |
Correct |
102 ms |
5348 KB |
Output is correct |
| 13 |
Correct |
125 ms |
9020 KB |
Output is correct |
| 14 |
Correct |
103 ms |
5348 KB |
Output is correct |
| 15 |
Correct |
76 ms |
5348 KB |
Output is correct |
| 16 |
Correct |
132 ms |
13668 KB |
Output is correct |
| 17 |
Correct |
130 ms |
8932 KB |
Output is correct |
| 18 |
Correct |
99 ms |
8300 KB |
Output is correct |
| 19 |
Correct |
99 ms |
5476 KB |
Output is correct |
| 20 |
Correct |
104 ms |
5348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
74 ms |
31804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
