oj.uz

Submission #388355

# Submission time Handle Problem Language Result Execution time Memory
388355 2021-04-11T05:03:35 Z clifter None (KOI18_matrix) C++14
23 / 100
 4000 ms 18756 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[505000];
int* maxtree[500500];
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);
  
  
  int maxs = -1;
  for(int i=1; i<=m; i++){
    ans[i] = 1;
    for(int j=1; j<i; j++){

      if(p[j].y<=p[i].y&&p[j].z<=p[i].z) {
        if(ans[i]<ans[j]+1) ans[i] = ans[j]+1;
      }

    }
    if(maxs<ans[i]) maxs = ans[i];
  }

  cout<<maxs;

  
}

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]);
      |                    ~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 12532 KB Output is correct
2 Correct 134 ms 12496 KB Output is correct
3 Correct 112 ms 12492 KB Output is correct
4 Correct 181 ms 12744 KB Output is correct
5 Correct 151 ms 12628 KB Output is correct
6 Correct 64 ms 12500 KB Output is correct
7 Correct 208 ms 12516 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 12616 KB Output is correct
2 Correct 215 ms 12604 KB Output is correct
3 Correct 155 ms 12492 KB Output is correct
4 Correct 267 ms 12664 KB Output is correct
5 Correct 132 ms 12652 KB Output is correct
6 Correct 67 ms 12548 KB Output is correct
7 Correct 217 ms 12524 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 12532 KB Output is correct
2 Correct 134 ms 12496 KB Output is correct
3 Correct 112 ms 12492 KB Output is correct
4 Correct 181 ms 12744 KB Output is correct
5 Correct 151 ms 12628 KB Output is correct
6 Correct 64 ms 12500 KB Output is correct
7 Correct 208 ms 12516 KB Output is correct
8 Execution timed out 4091 ms 17928 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 12616 KB Output is correct
2 Correct 215 ms 12604 KB Output is correct
3 Correct 155 ms 12492 KB Output is correct
4 Correct 267 ms 12664 KB Output is correct
5 Correct 132 ms 12652 KB Output is correct
6 Correct 67 ms 12548 KB Output is correct
7 Correct 217 ms 12524 KB Output is correct
8 Execution timed out 4072 ms 18756 KB Time limit exceeded
9 Halted 0 ms 0 KB -