Submission #63149

#	Time	Username	Problem	Language	Result	Execution time	Memory
63149		khsoo01	조화행렬 (KOI18_matrix)	C++11	100 / 100	506 ms	152972 KiB

matrix

#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef pair<int,int> pii;

const int N = 200005;

int n, m, a[3][N], cc, ans;
vector<pair<int, pii> > v;
set<pii> s[N];

void upd (int I, int A, int B) {
	s[I].insert({A, B});
	{
		auto it = s[I].find({A, B});
		if(it != s[I].begin()) {
			it--;
			if(it->Y < B) {
				it++;
				s[I].erase(it);
				return;
			}
		}
	}
	while(true) {
		auto it = s[I].find({A, B});
		it++;
		if(it == s[I].end() || it->Y < B) break;
		else s[I].erase(it);
	}
}

bool get (int I, int A, int B) {
	auto it = s[I].lower_bound({A, 0});
	if(it == s[I].begin()) return false;
	it--;
	return (it->Y < B);
}

int main()
{
	scanf("%d%d",&m,&n);
	for(int i=0;i<m;i++) {
		for(int j=1;j<=n;j++) {
			scanf("%d",&a[i][j]);
		}
	}
	for(int i=1;i<=n;i++) {
		v.push_back({a[0][i], {a[1][i], a[2][i]}});
	}
	sort(v.begin(), v.end());
	for(auto &T : v) {
		int A, B;
		tie(A, B) = T.Y;
		if(B == 0) B = ++cc;
		int S = 0, E = n-1;
		while(S<E) {
			int M = (S+E)/2+1;
			get(M, A, B) ? S = M : E = M-1;
		}
		upd(S+1, A, B);
		ans = max(ans, S+1);
	}
	printf("%d\n",ans);
}

Compilation message (stderr)

matrix.cpp: In function 'int main()':
matrix.cpp:43: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:46: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: 62 / 62