Submission #167588

#	Time	Username	Problem	Language	Result	Execution time	Memory
167588		cgiosy	조화행렬 (KOI18_matrix)	C++17	100 / 100	2500 ms	277380 KiB

matrix

#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 (stderr)

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 / 14
• Subtask 2: 9 / 9
• Subtask 3: 15 / 15
• Subtask 4: 62 / 62