oj.uz

Submission #388338

# Submission time Handle Problem Language Result Execution time Memory
388338 2021-04-11T04:21:25 Z clifter None (KOI18_matrix) C++14
29 / 100
 733 ms 72664 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], maxtree[806000];
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 -1;
  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 = lower_bound(elem[node].begin(), elem[node].end(), z2)-elem[node].begin()+1;

  if(e<y1||s>y2) return -1;
  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].resize(4*elem[i].size()+1); 
  }

  


  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:24:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     while(pt1<elem[node*2].size()&&pt2<elem[node*2+1].size()){
      |           ~~~^~~~~~~~~~~~~~~~~~~~
matrix.cpp:24:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     while(pt1<elem[node*2].size()&&pt2<elem[node*2+1].size()){
      |                                    ~~~^~~~~~~~~~~~~~~~~~~~~~
matrix.cpp:37:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int i=pt1; i<elem[node*2].size(); i++) elem[node].push_back(elem[node*2][i]);
      |                    ~^~~~~~~~~~~~~~~~~~~~
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=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 44 ms 39880 KB Output is correct
2 Correct 40 ms 39896 KB Output is correct
3 Correct 37 ms 39820 KB Output is correct
4 Correct 37 ms 39880 KB Output is correct
5 Correct 37 ms 39888 KB Output is correct
6 Correct 35 ms 39772 KB Output is correct
7 Correct 36 ms 39840 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 80 ms 42584 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 39880 KB Output is correct
2 Correct 40 ms 39896 KB Output is correct
3 Correct 37 ms 39820 KB Output is correct
4 Correct 37 ms 39880 KB Output is correct
5 Correct 37 ms 39888 KB Output is correct
6 Correct 35 ms 39772 KB Output is correct
7 Correct 36 ms 39840 KB Output is correct
8 Correct 733 ms 72492 KB Output is correct
9 Correct 610 ms 72556 KB Output is correct
10 Correct 411 ms 72536 KB Output is correct
11 Correct 428 ms 72612 KB Output is correct
12 Correct 456 ms 72572 KB Output is correct
13 Correct 399 ms 72576 KB Output is correct
14 Correct 472 ms 72628 KB Output is correct
15 Correct 394 ms 72556 KB Output is correct
16 Correct 404 ms 72572 KB Output is correct
17 Correct 409 ms 72572 KB Output is correct
18 Correct 401 ms 72664 KB Output is correct
19 Correct 436 ms 72492 KB Output is correct
20 Correct 717 ms 72520 KB Output is correct

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Incorrect 80 ms 42584 KB Output isn't correct
2 Halted 0 ms 0 KB -