| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 388350 |
2021-04-11T04:51:16 Z |
clifter |
None (KOI18_matrix) |
C++14 |
|
718 ms |
60316 KB |
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct point{int x; int y; int z;};
bool cmpx(point a, point b) {return a.x<b.x;}
bool cmpy(point a, point b) {return a.y<b.y;}
int map[4][305000];
int arr[305000], ans[300500], ytoz[300500];
vector<int> elem[805000];
int* maxtree[800500];
point p[300500];
void init(int s, int e, int node){
if(s==e) elem[node].push_back(ytoz[s]);
else{
int mid = (s+e)/2;
init(s, mid, node*2);
init(mid+1, e, node*2+1);
int pt1 = 0, pt2 = 0;
while(pt1<elem[node*2].size()&&pt2<elem[node*2+1].size()){
if(elem[node*2][pt1]<elem[node*2+1][pt2]) elem[node].push_back(elem[node*2][pt1++]);
else if(elem[node*2][pt1]>elem[node*2+1][pt2]) elem[node].push_back(elem[node*2+1][pt2++]);
else{
elem[node].push_back(elem[node*2][pt1++]);
pt2++;
}
}
for(int i=pt1; i<elem[node*2].size(); i++) elem[node].push_back(elem[node*2][i]);
for(int i=pt2; i<elem[node*2+1].size(); i++) elem[node].push_back(elem[node*2+1][i]);
}
}
void insert_node(int pos, int val, int s, int e, int node, int nodez){
if(pos<s||pos>e) return;
maxtree[node][nodez] = (maxtree[node][nodez]<val)?val:maxtree[node][nodez];
if(s!=e){
insert_node(pos, val, s, (s+e)/2, node, nodez*2);
insert_node(pos, val, (s+e)/2+1, e, node, nodez*2+1);
}
}
void insert(int y, int z, int val, int s, int e, int node, int m){
if(y<s||y>e) return;
int coord = lower_bound(elem[node].begin(), elem[node].end(), z)-elem[node].begin()+1;
insert_node(coord, val, 1, elem[node].size(), node, 1);
if(s!=e){
insert(y,z,val,s,(s+e)/2,node*2,m);
insert(y,z,val,(s+e)/2+1,e,node*2+1,m);
}
}
int getmax_node(int z1, int z2, int s, int e, int node, int nodez){
if(e<z1||s>z2) return 0;
else if(z1<=s&&e<=z2) return maxtree[node][nodez];
else{
int a = getmax_node(z1, z2, s, (s+e)/2, node, nodez*2);
int b = getmax_node(z1, z2, (s+e)/2+1, e, node, nodez*2+1);
return a<b?b:a;
}
}
int getmax(int y1, int y2, int z1, int z2, int s, int e, int node, int m){
int c1 = lower_bound(elem[node].begin(), elem[node].end(), z1)-elem[node].begin()+1;
int c2 = upper_bound(elem[node].begin(), elem[node].end(), z2)-elem[node].begin();
if(e<y1||s>y2||c1>c2) return 0;
else if(y1<=s&&e<=y2) return getmax_node(c1, c2, 1, elem[node].size(), node, 1);
else{
int a = getmax(y1, y2, z1, z2, s, (s+e)/2, node*2, m);
int b = getmax(y1, y2, z1, z2, (s+e)/2+1, e, node*2+1, m);
return a>b?a:b;
}
}
int main() {
int n,m;
cin.sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin>>n>>m;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
cin>>arr[j];
//arr[j] = j;
map[i][j] = arr[j];
}
sort(arr+1, arr+m+1);
for(int j=1; j<=m; j++){
map[i][j] = lower_bound(arr+1, arr+m+1, map[i][j])-arr;
}
}
for(int j=1; j<=m; j++) {
p[j].x = map[1][j]; p[j].y = map[2][j]; p[j].z = (n==2)?1:map[3][j];
ytoz[p[j].y] = p[j].z;
}
sort(p+1, p+m+1, cmpx);
init(1, m, 1);
for(int i=1; i<=4*m; i++){
if(elem[i].size()!=0) maxtree[i] = new int[elem[i].size()*4+4];
}
int ans = -123;
for(int i=1; i<=m; i++){
int t = getmax(1, p[i].y, 1, p[i].z, 1, m, 1, m)+1;
if(ans<t) ans = t;
//cout<<t<<" ";
insert(p[i].y, p[i].z, t, 1, m, 1, m);
}
cout<<ans;
}
Compilation message
matrix.cpp: In function 'void init(int, int, int)':
matrix.cpp:25:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | while(pt1<elem[node*2].size()&&pt2<elem[node*2+1].size()){
| ~~~^~~~~~~~~~~~~~~~~~~~
matrix.cpp:25:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | while(pt1<elem[node*2].size()&&pt2<elem[node*2+1].size()){
| ~~~^~~~~~~~~~~~~~~~~~~~~~
matrix.cpp:38:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for(int i=pt1; i<elem[node*2].size(); i++) elem[node].push_back(elem[node*2][i]);
| ~^~~~~~~~~~~~~~~~~~~~
matrix.cpp:39:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for(int i=pt2; i<elem[node*2+1].size(); i++) elem[node].push_back(elem[node*2+1][i]);
| ~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
21384 KB |
Output is correct |
| 2 |
Correct |
26 ms |
21360 KB |
Output is correct |
| 3 |
Correct |
26 ms |
21356 KB |
Output is correct |
| 4 |
Correct |
26 ms |
21332 KB |
Output is correct |
| 5 |
Correct |
28 ms |
21364 KB |
Output is correct |
| 6 |
Correct |
27 ms |
21296 KB |
Output is correct |
| 7 |
Correct |
25 ms |
21324 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
62 ms |
23832 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
21384 KB |
Output is correct |
| 2 |
Correct |
26 ms |
21360 KB |
Output is correct |
| 3 |
Correct |
26 ms |
21356 KB |
Output is correct |
| 4 |
Correct |
26 ms |
21332 KB |
Output is correct |
| 5 |
Correct |
28 ms |
21364 KB |
Output is correct |
| 6 |
Correct |
27 ms |
21296 KB |
Output is correct |
| 7 |
Correct |
25 ms |
21324 KB |
Output is correct |
| 8 |
Correct |
659 ms |
60104 KB |
Output is correct |
| 9 |
Correct |
525 ms |
60152 KB |
Output is correct |
| 10 |
Correct |
397 ms |
60100 KB |
Output is correct |
| 11 |
Correct |
398 ms |
60132 KB |
Output is correct |
| 12 |
Correct |
447 ms |
60132 KB |
Output is correct |
| 13 |
Correct |
386 ms |
60188 KB |
Output is correct |
| 14 |
Correct |
426 ms |
60144 KB |
Output is correct |
| 15 |
Correct |
397 ms |
60168 KB |
Output is correct |
| 16 |
Correct |
405 ms |
60128 KB |
Output is correct |
| 17 |
Correct |
379 ms |
60308 KB |
Output is correct |
| 18 |
Correct |
384 ms |
60220 KB |
Output is correct |
| 19 |
Correct |
412 ms |
60316 KB |
Output is correct |
| 20 |
Correct |
718 ms |
60140 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
62 ms |
23832 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
