oj.uz

Submission #67342

# Submission time Handle Problem Language Result Execution time Memory
67342 2018-08-14T03:33:27 Z h0ngjun7 None (KOI18_matrix) C++17
100 / 100
 3151 ms 101464 KB 
#include <bits/stdc++.h>
using namespace std;
#define N (200000)
struct Node{
	int a[3];
	Node(){}
	Node(int x, int y, int z){a[0]=x;a[1]=y;a[2]=z;}
};
int ctl, tree[8*N], dp[N], n;;
int cmp(Node x, Node y){return x.a[ctl] < y.a[ctl];}
Node f[N], tmp1[N], tmp2[N];
vector<int> v;
void push(int x, int pos, int L, int R, int val){
	if(pos < L || pos > R)return;
	if(pos == L && pos == R){
		tree[x] = val;
		return;
	}
	int mid = (L+R)/2;
	push(2*x, pos, L, mid, val);
	push(2*x+1, pos, mid+1, R, val);
	tree[x] = max(tree[x*2], tree[2*x+1]);
	return;
}
int get(int x, int l, int r, int L, int R){
	if(l > R || r < L)return 0;
	if(l <= L && R <= r)return tree[x];
	int mid = (L + R) / 2;
	return max(get(2*x, l, r, L, mid), get(2*x+1, l, r, mid+1, R));
}
void solve(int l, int r){
	if(l == r){dp[l]++;return;}
	int mid = (l+r)/2;
	solve(l, mid);
	for(int i=l; i<=mid; i++)tmp1[i] = f[i], tmp1[i].a[0]=i;
	for(int i=mid+1; i<=r; i++)tmp2[i] = f[i], tmp2[i].a[0]=i;
	sort(tmp1+l, tmp1+mid+1, cmp);
	sort(tmp2+mid+1, tmp2+r+1, cmp);
	int ll=l, rr=mid+1;
	while(ll < mid+1 || rr <= r){
		if(ll < mid+1 && tmp1[ll].a[1] < tmp2[rr].a[1] || rr > r){
			push(1, tmp1[ll].a[2], 0, n-1, dp[tmp1[ll].a[0]]);
			ll++;
		}
		else{
			dp[tmp2[rr].a[0]] = max(get(1, 0, tmp2[rr].a[2]-1, 0, n-1), dp[tmp2[rr].a[0]]);
			rr++;
		}
	}
	for(int i=l; i<=mid; i++)push(1, tmp1[i].a[2], 0, n-1, 0);
	solve(mid+1, r);
}
int main(){
	int m,ans=0;
	scanf("%d %d", &m, &n);
	for(int i=0; i<m; i++)for(int j=0; j<n; j++)scanf("%d", &f[j].a[i]);
	sort(f, f+n, cmp);
	if(m == 2){
		v.push_back(0);
		for(int i=0; i<n; i++){
			auto it = lower_bound(v.begin(), v.end(), f[i].a[1]);
			if(it == v.end())v.push_back(f[i].a[1]);
			else *it = f[i].a[1];
		}
		printf("%d\n", v.size()-1);
	}
	else{
		ctl=1;
		for(int idx=1; idx<3; idx++){
			map<int, int> mp;
			for(int i=0; i<n; i++)mp[f[i].a[idx]]=0;
			int a = 0;
			for(auto it=mp.begin(); it != mp.end(); it++)it->second=a++;
			for(int i=0; i<n; i++)f[i].a[idx] = mp[f[i].a[idx]];
		}
		solve(0, n-1);
		for(int i=0; i<n; i++)ans=max(ans, dp[i]);
		printf("%d\n", ans);
	}
	return 0;
}

Compilation message

matrix.cpp: In function 'void solve(int, int)':
matrix.cpp:41:17: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   if(ll < mid+1 && tmp1[ll].a[1] < tmp2[rr].a[1] || rr > r){
      ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
matrix.cpp: In function 'int main()':
matrix.cpp:65:28: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
   printf("%d\n", v.size()-1);
                  ~~~~~~~~~~^
matrix.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &m, &n);
  ~~~~~^~~~~~~~~~~~~~~~~
matrix.cpp:56:51: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<m; i++)for(int j=0; j<n; j++)scanf("%d", &f[j].a[i]);
                                              ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 376 KB Output is correct
2 Correct 10 ms 612 KB Output is correct
3 Correct 10 ms 612 KB Output is correct
4 Correct 11 ms 612 KB Output is correct
5 Correct 12 ms 640 KB Output is correct
6 Correct 8 ms 664 KB Output is correct
7 Correct 9 ms 688 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 1468 KB Output is correct
2 Correct 66 ms 1584 KB Output is correct
3 Correct 82 ms 1596 KB Output is correct
4 Correct 74 ms 1596 KB Output is correct
5 Correct 54 ms 1640 KB Output is correct
6 Correct 49 ms 1640 KB Output is correct
7 Correct 68 ms 1724 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 376 KB Output is correct
2 Correct 10 ms 612 KB Output is correct
3 Correct 10 ms 612 KB Output is correct
4 Correct 11 ms 612 KB Output is correct
5 Correct 12 ms 640 KB Output is correct
6 Correct 8 ms 664 KB Output is correct
7 Correct 9 ms 688 KB Output is correct
8 Correct 130 ms 2940 KB Output is correct
9 Correct 134 ms 2980 KB Output is correct
10 Correct 144 ms 3360 KB Output is correct
11 Correct 139 ms 3360 KB Output is correct
12 Correct 158 ms 3360 KB Output is correct
13 Correct 132 ms 3636 KB Output is correct
14 Correct 125 ms 3636 KB Output is correct
15 Correct 116 ms 3636 KB Output is correct
16 Correct 139 ms 4080 KB Output is correct
17 Correct 203 ms 4080 KB Output is correct
18 Correct 141 ms 4080 KB Output is correct
19 Correct 189 ms 4080 KB Output is correct
20 Correct 138 ms 4080 KB Output is correct

Subtask #4
62.0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 1468 KB Output is correct
2 Correct 66 ms 1584 KB Output is correct
3 Correct 82 ms 1596 KB Output is correct
4 Correct 74 ms 1596 KB Output is correct
5 Correct 54 ms 1640 KB Output is correct
6 Correct 49 ms 1640 KB Output is correct
7 Correct 68 ms 1724 KB Output is correct
8 Correct 1850 ms 19980 KB Output is correct
9 Correct 2168 ms 19980 KB Output is correct
10 Correct 1550 ms 19980 KB Output is correct
11 Correct 1584 ms 20076 KB Output is correct
12 Correct 2341 ms 20076 KB Output is correct
13 Correct 1633 ms 20076 KB Output is correct
14 Correct 1987 ms 20120 KB Output is correct
15 Correct 1497 ms 20120 KB Output is correct
16 Correct 1403 ms 20120 KB Output is correct
17 Correct 2170 ms 20120 KB Output is correct
18 Correct 3151 ms 20120 KB Output is correct
19 Correct 2245 ms 25784 KB Output is correct
20 Correct 1892 ms 31512 KB Output is correct
21 Correct 1554 ms 37452 KB Output is correct
22 Correct 3108 ms 43236 KB Output is correct
23 Correct 2100 ms 49204 KB Output is correct
24 Correct 2080 ms 54864 KB Output is correct
25 Correct 2246 ms 60776 KB Output is correct
26 Correct 2449 ms 66564 KB Output is correct
27 Correct 2206 ms 72408 KB Output is correct
28 Correct 1506 ms 78292 KB Output is correct
29 Correct 2126 ms 84004 KB Output is correct
30 Correct 1970 ms 89680 KB Output is correct
31 Correct 2522 ms 95616 KB Output is correct
32 Correct 2087 ms 101464 KB Output is correct