oj.uz

Submission #172337

# Submission time Handle Problem Language Result Execution time Memory
172337 2020-01-01T10:03:23 Z dennisstar None (KOI18_matrix) C++11
38 / 100
 4000 ms 512228 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define ryan bear
#define all(V) ((V).begin()), ((V).end())
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef vector<int> vim;
typedef vector<ll> vlm;

int lis(vector<pii> V) {
	sort(V.begin(), V.end());
	int stk[200010], tp=1;
	stk[0]=-1;
	for (int i=0; i<V.size(); i++) {
		if (stk[tp-1]<V[i].se) {
			stk[tp++]=V[i].se;
			continue;
		}
		int j=lower_bound(stk, stk+tp, V[i].se)-stk;
		stk[j]=V[i].se;
	}
	return tp-1;
}

int R, C;
struct dty {
	dty *l, *r;
	int dt, L, R; int Key;
	int md;
	dty(int k) {Key=k; dt=0; l=r=NULL;}
	inline void upd(int y, int val, int ys, int ye) {
		md=(ys+ye)/2;
		if (Key) {
			if (Key==y) {dt=max(dt, val); return ;}
			if (Key<=md) { l=new dty(Key); l->dt=dt; }
			else { r=new dty(Key); r->dt=dt; }
			Key=0;
		}
		if (y<=md) {
			if (!l) l=new dty(y);
			l->upd(y, val, ys, md);
		}
		else {
			if (!r) r=new dty(y);
			r->upd(y, val, md+1, ye);
		}
		L=(l?l->dt:0);
		R=(r?r->dt:0);
		dt=max(L, R);
	}
	inline int get(int y1, int y2, int ys, int ye) {
		md=(ys+ye)/2;
		if (Key) return (y1<=Key&&Key<=y2)?dt:0;
		if (y1<=ys&&ye<=y2) return dt;
		L=R=0;
		if (!(md<y1)) L=(l?(l->get(y1, y2, ys, md)):0);
		if (md+1<=y2&&md+1<=ye) R=(r?r->get(y1, y2, md+1, ye):0);
		return max(L, R);
	}
};

struct dtx {
	dty *seg;
	dtx *l, *r;
	int md;
	int L, R;
	dtx() {l=r=NULL; seg=NULL;}
	inline void upd(int x, int y, int val, int xs, int xe) {
		if (!seg) seg=new dty(y);
		seg->upd(y, val, 1, C);
		if (xs==xe) return ;
		md=(xs+xe)/2;
		if (x<=md) {
			if (!l) l=new dtx();
			l->upd(x, y, val, xs, md);
		}
		else {
			if (!r) r=new dtx();
			r->upd(x, y, val, md+1, xe);
		}
	}
	inline int get(int x1, int y1, int x2, int y2, int xs, int xe) {
		if (!seg) return 0;
		if (x1<=xs&&xe<=x2) return seg->get(y1, y2, 1, C);
		md=(xs+xe)/2;
		L=R=0;
		if (x1<=md) L=(l?(l->get(x1, y1, x2, y2, xs, md)):0);
		if (md+1<=x2&&md+1<=xe) R=(r?(r->get(x1, y1, x2, y2, md+1, xe)):0);
		return max(L, R);
	}
};

dtx *root=new dtx();

int M, N;

int main() {
	scanf("%d %d", &M, &N); R=C=N;
	if (M==2) {
		vector<pii> ar(N);
		for (int i=0; i<N; i++) scanf("%d", &ar[i].fi);
		for (int i=0; i<N; i++) scanf("%d", &ar[i].se);
		printf("%d\n", lis(ar));
		return 0;
	}
	else {
		vector<pair<int, pii> > ar(N);
		for (int i=0; i<N; i++) scanf("%d", &ar[i].fi);
		for (int i=0; i<N; i++) scanf("%d", &ar[i].se.fi);
		for (int i=0; i<N; i++) scanf("%d", &ar[i].se.se);
		vim cp1, cp2;
		sort(all(ar));
		for (auto pi:ar) { cp1.push_back(pi.se.fi); cp2.push_back(pi.se.se); }
		sort(all(cp1)); sort(all(cp2));
		cp1.erase(unique(all(cp1)), cp1.end()); cp2.erase(unique(all(cp2)), cp2.end());
		for (int i=0; i<N; i++) {
			ar[i].se.fi=lower_bound(all(cp1), ar[i].se.fi)-cp1.begin()+1;
			ar[i].se.se=lower_bound(all(cp2), ar[i].se.se)-cp2.begin()+1;
			int im=root->get(1, 1, ar[i].se.fi, ar[i].se.se, 1, R);
			root->upd(ar[i].se.fi, ar[i].se.se, im+1, 1, R);
		}
		printf("%d\n", root->get(1, 1, R, C, 1, R));
	}
	return 0;
}

Compilation message

matrix.cpp: In function 'int lis(std::vector<std::pair<int, int> >)':
matrix.cpp:18:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<V.size(); i++) {
                ~^~~~~~~~~
matrix.cpp: In function 'int main()':
matrix.cpp:102:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &M, &N); R=C=N;
  ~~~~~^~~~~~~~~~~~~~~~~
matrix.cpp:105:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for (int i=0; i<N; i++) scanf("%d", &ar[i].fi);
                           ~~~~~^~~~~~~~~~~~~~~~~
matrix.cpp:106:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for (int i=0; i<N; i++) scanf("%d", &ar[i].se);
                           ~~~~~^~~~~~~~~~~~~~~~~
matrix.cpp:112:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for (int i=0; i<N; i++) scanf("%d", &ar[i].fi);
                           ~~~~~^~~~~~~~~~~~~~~~~
matrix.cpp:113:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for (int i=0; i<N; i++) scanf("%d", &ar[i].se.fi);
                           ~~~~~^~~~~~~~~~~~~~~~~~~~
matrix.cpp:114:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for (int i=0; i<N; i++) scanf("%d", &ar[i].se.se);
                           ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 760 KB Output is correct
2 Correct 7 ms 632 KB Output is correct
3 Correct 7 ms 632 KB Output is correct
4 Correct 7 ms 760 KB Output is correct
5 Correct 7 ms 632 KB Output is correct
6 Correct 7 ms 760 KB Output is correct
7 Correct 7 ms 760 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 18296 KB Output is correct
2 Correct 56 ms 18980 KB Output is correct
3 Correct 67 ms 17016 KB Output is correct
4 Correct 80 ms 16504 KB Output is correct
5 Correct 61 ms 17656 KB Output is correct
6 Correct 54 ms 19704 KB Output is correct
7 Correct 78 ms 16632 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 760 KB Output is correct
2 Correct 7 ms 632 KB Output is correct
3 Correct 7 ms 632 KB Output is correct
4 Correct 7 ms 760 KB Output is correct
5 Correct 7 ms 632 KB Output is correct
6 Correct 7 ms 760 KB Output is correct
7 Correct 7 ms 760 KB Output is correct
8 Correct 111 ms 7288 KB Output is correct
9 Correct 109 ms 7416 KB Output is correct
10 Correct 105 ms 7516 KB Output is correct
11 Correct 99 ms 7308 KB Output is correct
12 Correct 109 ms 7572 KB Output is correct
13 Correct 105 ms 7812 KB Output is correct
14 Correct 108 ms 7416 KB Output is correct
15 Correct 101 ms 7420 KB Output is correct
16 Correct 101 ms 8100 KB Output is correct
17 Correct 104 ms 7720 KB Output is correct
18 Correct 104 ms 7736 KB Output is correct
19 Correct 106 ms 7436 KB Output is correct
20 Correct 112 ms 7312 KB Output is correct

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 18296 KB Output is correct
2 Correct 56 ms 18980 KB Output is correct
3 Correct 67 ms 17016 KB Output is correct
4 Correct 80 ms 16504 KB Output is correct
5 Correct 61 ms 17656 KB Output is correct
6 Correct 54 ms 19704 KB Output is correct
7 Correct 78 ms 16632 KB Output is correct
8 Correct 1700 ms 469100 KB Output is correct
9 Correct 2352 ms 456072 KB Output is correct
10 Correct 1569 ms 495056 KB Output is correct
11 Correct 1494 ms 508896 KB Output is correct
12 Correct 2005 ms 422116 KB Output is correct
13 Correct 1602 ms 481448 KB Output is correct
14 Correct 2530 ms 445440 KB Output is correct
15 Correct 1556 ms 512228 KB Output is correct
16 Correct 1528 ms 510788 KB Output is correct
17 Correct 2337 ms 456036 KB Output is correct
18 Execution timed out 4067 ms 386308 KB Time limit exceeded
19 Halted 0 ms 0 KB -