oj.uz

Submission #167588

# Submission time Handle Problem Language Result Execution time Memory
167588 2019-12-09T04:15:28 Z cgiosy None (KOI18_matrix) C++17
100 / 100
 2500 ms 277380 KB 
#include <bits/stdc++.h>
using namespace std;

struct T { int x, l, r; };
vector<T> X;
struct seg {
	int N, root;
	seg(const int sz) : N(sz-1) { root=-1; }
	int get(int l, int r, int s, int e, int i) const {
		if(i==-1 || e<l || r<s) return 0;
		if(l<=s && e<=r) return X[i].x;
		int m=(s+e)>>1;
		return max(get(l, r, s, m, X[i].l), get(l, r, m+1, e, X[i].r));
	}
	int get(int r) const { return get(0, r, 0, N, root); }
	void set(int p, int x, int s, int e, int&i) {
		if(p<s || e<p) return;
		if(i==-1) {
			i=X.size();
			X.push_back({0, -1, -1});
		}
		X[i].x=max(X[i].x, x);
		if(s==e) return;
		int m=(s+e)>>1;
		set(p, x, s, m, X[i].l), set(p, x, m+1, e, X[i].r);
	}
	void set(int p, int x) { set(p, x, 0, N, root); }
};
int main() {
	X.reserve(1<<25);
	ios_base::sync_with_stdio(false);cin.tie(nullptr);
	int M, N;
	cin>>M>>N;
	if(M==2) {
		vector<pair<int, int>> A(N);
		for(auto&[x,y]:A) cin>>x;
		for(auto&[x,y]:A) cin>>y;
		sort(begin(A), end(A));
		vector<int> B(N, 1e9);
		for(auto[x,y]:A) *lower_bound(begin(B), end(B), y)=y;
		cout<<lower_bound(begin(B), end(B), 1e9)-begin(B);
		return 0;
	}
	struct iii {
		int i, x, y;
		bool operator<(const iii& b) const { return i<b.i; }
	};
	vector<iii> A(N);
	vector<int> B(M=2*N); B.clear();
	for(auto&[i,x,y]:A) cin>>i;
	for(auto&[i,x,y]:A) cin>>x, B.push_back(x);
	for(auto&[i,x,y]:A) cin>>y, B.push_back(y);
	sort(begin(A), end(A));
	sort(begin(B), end(B));
	#define pos(x) lower_bound(begin(B), end(B), x)-begin(B)
	for(auto&[i,x,y]:A) x=pos(x), y=pos(y);
	vector<seg> T(M+1, seg(M));
	int m=0;
	for(auto[i,x,y]:A) {
		int n=0;
		for(int i=x+1; i; i-=i&-i) n=max(n, T[i].get(y));
		m=max(m, ++n);
		for(int i=x+1; i<=M; i+=i&-i) T[i].set(y, n);
	}
	cout<<m;
}

Compilation message

matrix.cpp: In function 'int main()':
matrix.cpp:36:16: warning: unused variable 'y' [-Wunused-variable]
   for(auto&[x,y]:A) cin>>x;
                ^
matrix.cpp:37:16: warning: unused variable 'x' [-Wunused-variable]
   for(auto&[x,y]:A) cin>>y;
                ^
matrix.cpp:40:15: warning: unused variable 'x' [-Wunused-variable]
   for(auto[x,y]:A) *lower_bound(begin(B), end(B), y)=y;
               ^
matrix.cpp:50:17: warning: unused variable 'x' [-Wunused-variable]
  for(auto&[i,x,y]:A) cin>>i;
                 ^
matrix.cpp:50:17: warning: unused variable 'y' [-Wunused-variable]
matrix.cpp:51:17: warning: unused variable 'i' [-Wunused-variable]
  for(auto&[i,x,y]:A) cin>>x, B.push_back(x);
                 ^
matrix.cpp:51:17: warning: unused variable 'y' [-Wunused-variable]
matrix.cpp:52:17: warning: unused variable 'i' [-Wunused-variable]
  for(auto&[i,x,y]:A) cin>>y, B.push_back(y);
                 ^
matrix.cpp:52:17: warning: unused variable 'x' [-Wunused-variable]
matrix.cpp:56:17: warning: unused variable 'i' [-Wunused-variable]
  for(auto&[i,x,y]:A) x=pos(x), y=pos(y);
                 ^
matrix.cpp:59:16: warning: unused variable 'i' [-Wunused-variable]
  for(auto[i,x,y]:A) {
                ^

Subtask #1
14.0 / 14.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 6264 KB Output is correct
2 Correct 34 ms 5880 KB Output is correct
3 Correct 44 ms 8096 KB Output is correct
4 Correct 49 ms 9336 KB Output is correct
5 Correct 39 ms 7160 KB Output is correct
6 Correct 33 ms 5496 KB Output is correct
7 Correct 50 ms 9096 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 632 KB Output is correct
2 Correct 6 ms 632 KB Output is correct
3 Correct 6 ms 632 KB Output is correct
4 Correct 6 ms 636 KB Output is correct
5 Correct 6 ms 632 KB Output is correct
6 Correct 6 ms 632 KB Output is correct
7 Correct 6 ms 632 KB Output is correct
8 Correct 93 ms 6608 KB Output is correct
9 Correct 91 ms 6556 KB Output is correct
10 Correct 90 ms 6612 KB Output is correct
11 Correct 83 ms 6648 KB Output is correct
12 Correct 93 ms 6664 KB Output is correct
13 Correct 92 ms 6552 KB Output is correct
14 Correct 90 ms 6520 KB Output is correct
15 Correct 82 ms 6520 KB Output is correct
16 Correct 92 ms 6648 KB Output is correct
17 Correct 92 ms 6648 KB Output is correct
18 Correct 89 ms 6520 KB Output is correct
19 Correct 90 ms 6560 KB Output is correct
20 Correct 93 ms 6556 KB Output is correct

Subtask #4
62.0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 6264 KB Output is correct
2 Correct 34 ms 5880 KB Output is correct
3 Correct 44 ms 8096 KB Output is correct
4 Correct 49 ms 9336 KB Output is correct
5 Correct 39 ms 7160 KB Output is correct
6 Correct 33 ms 5496 KB Output is correct
7 Correct 50 ms 9096 KB Output is correct
8 Correct 1014 ms 162936 KB Output is correct
9 Correct 1297 ms 210648 KB Output is correct
10 Correct 899 ms 136704 KB Output is correct
11 Correct 882 ms 130556 KB Output is correct
12 Correct 1233 ms 277184 KB Output is correct
13 Correct 977 ms 146856 KB Output is correct
14 Correct 1391 ms 211192 KB Output is correct
15 Correct 911 ms 130244 KB Output is correct
16 Correct 898 ms 130248 KB Output is correct
17 Correct 1315 ms 210844 KB Output is correct
18 Correct 2500 ms 277296 KB Output is correct
19 Correct 1632 ms 277328 KB Output is correct
20 Correct 1143 ms 184440 KB Output is correct
21 Correct 889 ms 130424 KB Output is correct
22 Correct 2478 ms 269588 KB Output is correct
23 Correct 1302 ms 210580 KB Output is correct
24 Correct 1605 ms 277372 KB Output is correct
25 Correct 1978 ms 241852 KB Output is correct
26 Correct 1469 ms 130424 KB Output is correct
27 Correct 1200 ms 277380 KB Output is correct
28 Correct 878 ms 130152 KB Output is correct
29 Correct 1210 ms 210404 KB Output is correct
30 Correct 1310 ms 210332 KB Output is correct
31 Correct 1600 ms 130472 KB Output is correct
32 Correct 1279 ms 210936 KB Output is correct