oj.uz

Submission #172353

# Submission time Handle Problem Language Result Execution time Memory
172353 2020-01-01T10:44:27 Z dennisstar None (KOI18_matrix) C++11
100 / 100
 841 ms 126708 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;
}


struct Seg {
	Seg *l, *r;
	int dt;
	Seg() {l=r=NULL; dt=(1<<30);}
	void upd(int i, int xs, int xe, int val) {
		dt=min(dt, val);
		if (xs==xe) return ;
		int md=(xs+xe)/2;
		if (i<=md) {
			if (!l) l=new Seg();
			l->upd(i, xs, md, val);
		}
		else {
			if (!r) r=new Seg();
			r->upd(i, md+1, xe, val);
		}
	}
	int get(int s, int e, int xs, int xe) {
		if (xs>xe) return (1<<30);
		if (s<=xs&&xe<=e) return dt;
		int L, R; L=R=(1<<30);
		int md=(xs+xe)/2;
		if (s<=md) L=(l?l->get(s, e, xs, md):(1<<30));
		if (md+1<=e) R=(r?r->get(s, e, md+1, xe):(1<<30));
		return min(L, R);
	}
};

int M, N;
Seg *tree[200010];

int main() {
	scanf("%d %d", &M, &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 mx=0, s, e;
		for (int i=0; i<=N; i++) tree[i]=new Seg();
		tree[0]->upd(0, 1, N, 0);
		for (int i=0; i<N; i++) {
			if (!mx) {
				mx=1;
				tree[1]->upd(ar[i].se.fi, 1, N, ar[i].se.se);
				continue;
			}
			s=0, e=mx+1;
			while (s+1<e) {
				int md=(s+e)/2;
				if (tree[md]->get(1, ar[i].se.fi, 1, N) <= ar[i].se.se) s=md;
				else e=md;
			}
			mx=max(s+1, mx);
			tree[s+1]->upd(ar[i].se.fi, 1, N, ar[i].se.se);
		}
		printf("%d", mx);
	}
	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:62: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:65: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:66: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:72: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:73: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:74: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 632 KB Output is correct
2 Correct 7 ms 632 KB Output is correct
3 Correct 7 ms 760 KB Output is correct
4 Correct 7 ms 760 KB Output is correct
5 Correct 7 ms 760 KB Output is correct
6 Correct 6 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 20 ms 2936 KB Output is correct
2 Correct 20 ms 3192 KB Output is correct
3 Correct 22 ms 3064 KB Output is correct
4 Correct 23 ms 3164 KB Output is correct
5 Correct 20 ms 2936 KB Output is correct
6 Correct 24 ms 5368 KB Output is correct
7 Correct 23 ms 3168 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 632 KB Output is correct
2 Correct 7 ms 632 KB Output is correct
3 Correct 7 ms 760 KB Output is correct
4 Correct 7 ms 760 KB Output is correct
5 Correct 7 ms 760 KB Output is correct
6 Correct 6 ms 760 KB Output is correct
7 Correct 7 ms 760 KB Output is correct
8 Correct 107 ms 3900 KB Output is correct
9 Correct 106 ms 3832 KB Output is correct
10 Correct 102 ms 3988 KB Output is correct
11 Correct 95 ms 3832 KB Output is correct
12 Correct 105 ms 4036 KB Output is correct
13 Correct 102 ms 4188 KB Output is correct
14 Correct 104 ms 3960 KB Output is correct
15 Correct 96 ms 3832 KB Output is correct
16 Correct 96 ms 4600 KB Output is correct
17 Correct 101 ms 4216 KB Output is correct
18 Correct 101 ms 4256 KB Output is correct
19 Correct 103 ms 4088 KB Output is correct
20 Correct 108 ms 3832 KB Output is correct

Subtask #4
62.0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2936 KB Output is correct
2 Correct 20 ms 3192 KB Output is correct
3 Correct 22 ms 3064 KB Output is correct
4 Correct 23 ms 3164 KB Output is correct
5 Correct 20 ms 2936 KB Output is correct
6 Correct 24 ms 5368 KB Output is correct
7 Correct 23 ms 3168 KB Output is correct
8 Correct 439 ms 49452 KB Output is correct
9 Correct 334 ms 25188 KB Output is correct
10 Correct 465 ms 60260 KB Output is correct
11 Correct 640 ms 122864 KB Output is correct
12 Correct 282 ms 24676 KB Output is correct
13 Correct 439 ms 50404 KB Output is correct
14 Correct 515 ms 56292 KB Output is correct
15 Correct 535 ms 120880 KB Output is correct
16 Correct 555 ms 120804 KB Output is correct
17 Correct 316 ms 24676 KB Output is correct
18 Correct 841 ms 59152 KB Output is correct
19 Correct 343 ms 30476 KB Output is correct
20 Correct 464 ms 57828 KB Output is correct
21 Correct 552 ms 126708 KB Output is correct
22 Correct 740 ms 67864 KB Output is correct
23 Correct 316 ms 30452 KB Output is correct
24 Correct 349 ms 30528 KB Output is correct
25 Correct 620 ms 66024 KB Output is correct
26 Correct 385 ms 30564 KB Output is correct
27 Correct 283 ms 30408 KB Output is correct
28 Correct 549 ms 126548 KB Output is correct
29 Correct 312 ms 30436 KB Output is correct
30 Correct 314 ms 30436 KB Output is correct
31 Correct 389 ms 30708 KB Output is correct
32 Correct 316 ms 30436 KB Output is correct