oj.uz

Submission #127839

# Submission time Handle Problem Language Result Execution time Memory
127839 2019-07-10T07:01:51 Z junhopark None (KOI18_matrix) C++14
38 / 100
 4000 ms 505388 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define all(V) (V).begin(),(V).end()
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int SZ = 2e5+5;
struct data{int x, y, z;}p[SZ];
struct node
{
	int val, l, r;
	node() {}
	node(int val, int l, int r):val(val),l(l),r(r) {}
};
int n, m, res, ans;
vector<node> tree, emp;
vector<vector<node>> sub;
vector<int> u, v, w, lis;
bool comp(data l, data r) {return l.x<r.x;}
void compress()
{
	for (int i=1; i<=n; i++) {
		u.eb(p[i].x);
		v.eb(p[i].y);
		w.eb(p[i].z);
	}
	sort(all(u));
	sort(all(v));
	sort(all(w));
	u.erase(unique(all(u)),u.end());
	v.erase(unique(all(v)),v.end());
	w.erase(unique(all(w)),w.end());
	for (int i=1; i<=n; i++) {
		p[i].x=upper_bound(all(u),p[i].x)-u.begin();
		p[i].y=upper_bound(all(v),p[i].y)-v.begin();
		p[i].z=upper_bound(all(w),p[i].z)-w.begin();
	}
}
int get_sub_max(int si, int ei, int s, int e, int ind, int pnd)
{
	if (si>e||ei<s) return 0;
	if (si>=s&&ei<=e) return sub[pnd][ind].val;
	int mi=si+ei>>1;
	if (sub[pnd][ind].l<0) {
		sub[pnd][ind].l=sub[pnd].size();
		sub[pnd].eb(0,-1,-1);
	}
	if (sub[pnd][ind].r<0) {
		sub[pnd][ind].r=sub[pnd].size();
		sub[pnd].eb(0,-1,-1);
	}
	return max(get_sub_max(si,mi,s,e,sub[pnd][ind].l,pnd),get_sub_max(mi+1,ei,s,e,sub[pnd][ind].r,pnd));
}
int get_max(int si, int ei, int s, int e, int ns, int ne, int ind)
{
	if (si>e||ei<s) return 0;
	if (si>=s&&ei<=e) {
		if (!sub[ind].size()) sub[ind].eb(0,-1,-1);
		return get_sub_max(1, n, ns, ne, 0, ind);
	}
	int mi=si+ei>>1;
	if (tree[ind].l<0) {
		tree[ind].l=tree.size();
		tree.eb(0,-1,-1);
		sub.eb(emp);
	}
	if (tree[ind].r<0) {
		tree[ind].r=tree.size();
		tree.eb(0,-1,-1);
		sub.eb(emp);
	}
	return max(get_max(si,mi,s,e,ns,ne,tree[ind].l),get_max(mi+1,ei,s,e,ns,ne,tree[ind].r));
}
void update_sub(int si, int ei, int pl, int val, int ind, int pnd)
{
	if (si>pl||ei<pl) return;
	if (si==ei) {
		sub[pnd][ind].val=val;
		return;
	}
	int mi=si+ei>>1;
	if (pl>mi) {
		if (sub[pnd][ind].r<0) {
			sub[pnd][ind].r=sub[pnd].size();
			sub[pnd].eb(0,-1,-1);
		}
		update_sub(mi+1,ei,pl,val,sub[pnd][ind].r,pnd);
	}
	else {
		if (sub[pnd][ind].l<0) {
			sub[pnd][ind].l=sub[pnd].size();
			sub[pnd].eb(0,-1,-1);
		}
		update_sub(si,mi,pl,val,sub[pnd][ind].l,pnd);
	}
	sub[pnd][ind].val=0;
	if (sub[pnd][ind].l>=0) sub[pnd][ind].val=max(sub[pnd][ind].val,sub[pnd][sub[pnd][ind].l].val);
	if (sub[pnd][ind].r>=0) sub[pnd][ind].val=max(sub[pnd][ind].val,sub[pnd][sub[pnd][ind].r].val);
}
void update(int si, int ei, int pl, int np, int val, int ind)
{
	if (si>pl||ei<pl) return;
	if (!sub[ind].size()) sub[ind].eb(0,-1,-1);
	update_sub(1, n, np, val, 0, ind);
	if (si==ei) return;
	int mi=si+ei>>1;
	if (pl>mi) {
		if (tree[ind].r<0) {
			tree[ind].r=tree.size();
			tree.eb(0,-1,-1);
			sub.eb(emp);
		}
		update(mi+1,ei,pl,np,val,tree[ind].r);
	}
	else {
		if (tree[ind].l<0) {
			tree[ind].l=tree.size();
			tree.eb(0,-1,-1);
			sub.eb(emp);
		}
		update(si,mi,pl,np,val,tree[ind].l);
	}
	
}
int main()
{
	int i, j;
	scanf("%d %d", &m, &n);
	if (m==2) {
		for (i=1; i<=n; i++) scanf("%d", &p[i].x);
		for (i=1; i<=n; i++) scanf("%d", &p[i].y);
		compress();
		sort(p+1, p+n+1, comp);
		for (i=1; i<=n; i++) {
			int pl=lower_bound(all(lis),p[i].y)-lis.begin();
			if (pl==lis.size()) lis.eb(p[i].y);
			else lis[pl]=p[i].y;
		}
		printf("%d\n", lis.size());
	}
	else {
		for (i=1; i<=n; i++) scanf("%d", &p[i].x);
		for (i=1; i<=n; i++) scanf("%d", &p[i].y);
		for (i=1; i<=n; i++) scanf("%d", &p[i].z);
		compress();
		sort(p+1, p+n+1, comp);
		tree.eb(0,-1,-1);
		sub.eb(emp);
		for (i=1; i<=n; i++) {
			res=get_max(1, n, 1, p[i].y, 1, p[i].z, 0)+1;
			update(1, n, p[i].y, p[i].z, res, 0);
			ans=max(ans,res);
		}
		printf("%d\n", ans);
	}
	return 0;
}

Compilation message

matrix.cpp: In function 'int get_sub_max(int, int, int, int, int, int)':
matrix.cpp:48:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mi=si+ei>>1;
         ~~^~~
matrix.cpp: In function 'int get_max(int, int, int, int, int, int, int)':
matrix.cpp:66:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mi=si+ei>>1;
         ~~^~~
matrix.cpp: In function 'void update_sub(int, int, int, int, int, int)':
matrix.cpp:86:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mi=si+ei>>1;
         ~~^~~
matrix.cpp: In function 'void update(int, int, int, int, int, int)':
matrix.cpp:111:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mi=si+ei>>1;
         ~~^~~
matrix.cpp: In function 'int main()':
matrix.cpp:141:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (pl==lis.size()) lis.eb(p[i].y);
        ~~^~~~~~~~~~~~
matrix.cpp:144: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", lis.size());
                  ~~~~~~~~~~^
matrix.cpp:132:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
matrix.cpp:133: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:135:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for (i=1; i<=n; i++) scanf("%d", &p[i].x);
                        ~~~~~^~~~~~~~~~~~~~~
matrix.cpp:136:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for (i=1; i<=n; i++) scanf("%d", &p[i].y);
                        ~~~~~^~~~~~~~~~~~~~~
matrix.cpp:147:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for (i=1; i<=n; i++) scanf("%d", &p[i].x);
                        ~~~~~^~~~~~~~~~~~~~~
matrix.cpp:148:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for (i=1; i<=n; i++) scanf("%d", &p[i].y);
                        ~~~~~^~~~~~~~~~~~~~~
matrix.cpp:149:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for (i=1; i<=n; i++) scanf("%d", &p[i].z);
                        ~~~~~^~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 892 KB Output is correct
2 Correct 11 ms 888 KB Output is correct
3 Correct 11 ms 888 KB Output is correct
4 Correct 11 ms 888 KB Output is correct
5 Correct 11 ms 888 KB Output is correct
6 Correct 11 ms 888 KB Output is correct
7 Correct 12 ms 888 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 16684 KB Output is correct
2 Correct 97 ms 14708 KB Output is correct
3 Correct 141 ms 23584 KB Output is correct
4 Correct 190 ms 28924 KB Output is correct
5 Correct 208 ms 19796 KB Output is correct
6 Correct 89 ms 13032 KB Output is correct
7 Correct 175 ms 27472 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 892 KB Output is correct
2 Correct 11 ms 888 KB Output is correct
3 Correct 11 ms 888 KB Output is correct
4 Correct 11 ms 888 KB Output is correct
5 Correct 11 ms 888 KB Output is correct
6 Correct 11 ms 888 KB Output is correct
7 Correct 12 ms 888 KB Output is correct
8 Correct 240 ms 9048 KB Output is correct
9 Correct 251 ms 9060 KB Output is correct
10 Correct 230 ms 9436 KB Output is correct
11 Correct 223 ms 9072 KB Output is correct
12 Correct 235 ms 9052 KB Output is correct
13 Correct 239 ms 9812 KB Output is correct
14 Correct 232 ms 9052 KB Output is correct
15 Correct 223 ms 9180 KB Output is correct
16 Correct 232 ms 10460 KB Output is correct
17 Correct 231 ms 9992 KB Output is correct
18 Correct 232 ms 9836 KB Output is correct
19 Correct 235 ms 9180 KB Output is correct
20 Correct 234 ms 9052 KB Output is correct

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 16684 KB Output is correct
2 Correct 97 ms 14708 KB Output is correct
3 Correct 141 ms 23584 KB Output is correct
4 Correct 190 ms 28924 KB Output is correct
5 Correct 208 ms 19796 KB Output is correct
6 Correct 89 ms 13032 KB Output is correct
7 Correct 175 ms 27472 KB Output is correct
8 Correct 3407 ms 505388 KB Output is correct
9 Execution timed out 4045 ms 494492 KB Time limit exceeded
10 Halted 0 ms 0 KB -