Submission #172337

#	Time	Username	Problem	Language	Result	Execution time	Memory
172337		dennisstar	조화행렬 (KOI18_matrix)	C++11	38 / 100	4067 ms	512228 KiB

matrix

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

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