Submission #94475

#	Time	Username	Problem	Language	Result	Execution time	Memory
94475		edenooo	조화행렬 (KOI18_matrix)	C++17	0 / 100	39 ms	5240 KiB

matrix

#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<math.h>
#include<algorithm>
using namespace std;

#define INF 987654321
#define ll long long

int N, M;
vector<pair<int, pair<int, int> > > v;
vector<int> a, b, dp(200202, 1), seg(800808);

int Query(int L, int R, int n, int l, int r)
{
	if (r < L || R < l) return 0;
	if (L <= l && r <= R) return seg[n];
	int mid = (l + r) / 2;
	return max(Query(L, R, n * 2, l, mid), Query(L, R, n * 2 + 1, mid + 1, r));
}

int Update(int idx, int val, int n, int l, int r)
{
	if (r < idx || idx < l) return seg[n];
	if (l == r && l == idx) return seg[n] = val;
	int mid = (l + r) / 2;
	return seg[n] = max(Update(idx, val, n * 2, l, mid), Update(idx, val, n * 2 + 1, mid + 1, r));
}

void dnc(int l, int r)
{
	if (l == r) return;

	int mid = (l + r) / 2;
	dnc(l, mid);

	//propagate
	vector<pair<pair<int, int>, int> > u; //a b dp : 시간 인덱스 값

	for (int i = l; i <= mid; i++)
		u.push_back({ { a[i], b[i] }, dp[i] });
	sort(u.begin(), u.end());

	int pos = mid + 1;
	for (int i = 0; i < u.size(); i++)
	{
		while (pos <= r && a[pos] < u[i].first.first)
		{
			dp[pos] = max(dp[pos], Query(1, b[pos] - 1, 1, 1, N) + 1);
			pos++;
		}
		Update(u[i].first.second, u[i].second, 1, 1, N);
	}
	while (pos <= r)
	{
		dp[pos] = max(dp[pos], Query(1, b[pos] - 1, 1, 1, N) + 1);
		pos++;
	}

	for (int i = 0; i < u.size(); i++)
		Update(u[i].first.second, 0, 1, 1, N);

	u.clear();
	
	dnc(mid + 1, r);
}

int main()
{
	scanf("%d %d", &M, &N);
	v.resize(N);
	for (int i = 0; i < N; i++)
		scanf("%d", &v[i].first);
	for (int i = 0; i < N; i++)
		scanf("%d", &v[i].second.first);
	if (M == 3)
		for (int i = 0; i < N; i++)
			scanf("%d", &v[i].second.second);
	sort(v.begin(), v.end());
	if (M == 2)
		for (int i = 0; i < N; i++)
			v[i].second.second = i + 1;
	for (int i = 0; i < N; i++)
	{
		a.push_back(v[i].second.first);
		b.push_back(v[i].second.second);
	}

	//좌표 압축
	vector<pair<int, int> > aa, bb;
	for (int i = 0; i < N; i++)
	{
		aa.push_back({ a[i], i });
		bb.push_back({ b[i], i });
	}
	sort(aa.begin(), aa.end());
	sort(bb.begin(), bb.end());
	for (int i = 0; i < N; i++)
	{
		a[aa[i].second] = i + 1;
		b[bb[i].second] = i + 1;
	}

	dnc(0, N - 1); // T(n) = 2T(n/2) + O(nlogn)

	int res = 0;
	for (int i = 0; i < N; i++)
		res = max(res, dp[i]);
	printf("%d", res);
	return 0;
}

Compilation message (stderr)

matrix.cpp: In function 'void dnc(int, int)':
matrix.cpp:51:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < u.size(); i++)
                  ~~^~~~~~~~~~
matrix.cpp:66:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < u.size(); i++)
                  ~~^~~~~~~~~~
matrix.cpp: In function 'int main()':
matrix.cpp:76: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:79:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &v[i].first);
   ~~~~~^~~~~~~~~~~~~~~~~~~
matrix.cpp:81:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &v[i].second.first);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
matrix.cpp:84:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &v[i].second.second);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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