Submission #66191

#	Time	Username	Problem	Language	Result	Execution time	Memory
66191		junodeveloper	조화행렬 (KOI18_matrix)	C++17	38 / 100	4019 ms	199872 KiB

matrix

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
int m, n, a[4][200010];
vector<int> Ty[4*200010], tree[4*200010];
vector<pair<int, pair<int,int> > > Vq;
void Down(int h, int tl, int tr, int x, int y) {
	if(tr < x || x < tl) return;
	Ty[h].push_back(y);
	if(tl == tr) return;
	int mid = (tl + tr) / 2;
	Down(h*2, tl, mid, x, y); Down(h*2+1, mid+1, tr, x, y);
}
void build(int h, int tl, int tr) {
	sort(all(Ty[h]));
	Ty[h].erase(unique(all(Ty[h])), Ty[h].end());
	tree[h] = vector<int>(4*sz(Ty[h]));
	if(tl == tr) return;
	int mid = (tl + tr) / 2;
	build(h*2, tl, mid); build(h*2+1, mid+1, tr);
}
void update_y(int h1, int h2, int tl, int tr, int y, int v) {
	if(tr < y || y < tl) return;
	if(tl == tr) { tree[h1][h2] = v; return; }
	int mid = (tl + tr) / 2;
	update_y(h1, h2*2, tl, mid, y, v);
	update_y(h1, h2*2+1, mid+1, tr, y, v);
	tree[h1][h2] = max(tree[h1][h2*2], tree[h1][h2*2+1]);
}
void update(int h, int tl, int tr, int x, int y, int v) {
	if(tr < x || x < tl) return;
	update_y(h,1,0,sz(Ty[h])-1,lower_bound(all(Ty[h]),y)-Ty[h].begin(),v);
	if(tl == tr) return;
	int mid = (tl + tr) / 2;
	update(h*2, tl, mid, x,y,v);
	update(h*2+1, mid+1, tr, x,y,v);
}
int query_y(int h1, int h2, int tl, int tr, int l, int r) {
	if(l>r) return 0;
	if(tr < l || r < tl) return 0;
	if(l <= tl && tr <= r) return tree[h1][h2];
	int mid = (tl + tr) / 2;
	return max(query_y(h1,h2*2,tl,mid,l,r), query_y(h1,h2*2+1,mid+1,tr,l,r));
}
int query(int h, int tl, int tr, int x1, int y1, int x2, int y2) {
	if(x1>x2||y1>y2) return 0;
	if(tr < x1 || x2 < tl) return 0;
	if(x1 <= tl && tr <= x2) return
		query_y(h,1,0,sz(Ty[h])-1,lower_bound(all(Ty[h]),y1)-Ty[h].begin(),lower_bound(all(Ty[h]),y2+1)-Ty[h].begin()-1);
	int mid = (tl + tr) / 2;
	return max(query(h*2, tl, mid, x1,y1,x2,y2),
				query(h*2+1, mid+1, tr, x1,y1,x2,y2));
}
int main() {
	//clock_t start = clock();
	scanf("%d%d", &m, &n);
	for(int i=1; i<=m; i++) {
		vector<int> Vc;
		for(int j=1; j<=n; j++) {
			scanf("%d", &a[i][j]);
			Vc.push_back(a[i][j]);
		}
		sort(all(Vc));
		for(int j=1; j<=n; j++) {
			int c = lower_bound(all(Vc), a[i][j]) - Vc.begin();
			a[i][j] = c;
		}
	}
	for(int i=1; i<=n; i++) {
		int x = a[2][i], y = a[m == 3 ? 3 : 1][i];
		Vq.push_back({a[1][i], {x, y}});
		Down(1,0,n-1,x,y);
	}
	build(1,0,n-1);
	sort(all(Vq));
	int res = 0;
	for(auto& it : Vq) {
		int x=it.second.first,y=it.second.second,q=query(1,0,n-1,0,0,x-1,y-1);
		//printf("x:%d, y:%d, q:%d\n",x,y,q+1);
		update(1,0,n-1,x,y,q+1);
		res = max(res, q+1);
	}
	printf("%d", res);
	//printf("\n%lu", clock() - start);
	return 0;
}

Compilation message (stderr)

matrix.cpp: In function 'int main()':
matrix.cpp:59: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:63:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &a[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 9 / 9
• Subtask 3: 15 / 15
• Subtask 4: 0 / 62