답안 #388350

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
388350 2021-04-11T04:51:16 Z clifter 조화행렬 (KOI18_matrix) C++14
29 / 100
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]);
      |                    ~^~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 Grader output
1 Incorrect 62 ms 23832 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 Grader output
1 Incorrect 62 ms 23832 KB Output isn't correct
2 Halted 0 ms 0 KB -