Submission #112244

#	Time	Username	Problem	Language	Result	Execution time	Memory
112244		jhnah917	조화행렬 (KOI18_matrix)	C++14	0 / 100	20 ms	1024 KiB

matrix

#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
using namespace std;

struct Fenwick{
	int tree[202020];
	
	void update(int x, int v){
		x++;
		while(x < 202020){
			tree[x] = max(tree[x], v);
			x += x & -x;
		}
	}
	
	int query(int x){
		x++;
		int ret = 0;
		while(x){
			ret = max(ret, tree[x]);
			x -= x & -x;
		}
		return ret;
	}
	
	void set(int x){
		x++;
		//cout << "set : " << x << "\n";
		while(x < 202020){
			tree[x] = 0;
			x += x & -x;
		}
	}
}bit;

struct Node{
	int x, y, z;
	
	Node(int a, int b, int c) : x(a), y(b), z(c) {}
	Node() : Node(0, 0, 0) {}
	
	bool operator < (Node &rhs){
		if(x != rhs.x) return x < rhs.x;
		if(y != rhs.y) return y < rhs.y;
		return z < rhs.z;
	}
};

int n, m;
vector<Node> v;

int dp[202020];

void solve(int s, int e){
	if(s == e){
		dp[s]++; return;
	}
	int m = s + e >> 1;
	
	//left
	solve(s, m);
	
	//propagation : [s, m] -> [m+1, e]
	vector<Node> left, right;
	for(int i=s; i<=m; i++) left.push_back({v[i].y, v[i].z, dp[i]});
	for(int i=m+1; i<=e; i++) right.push_back({v[i].y, v[i].z, i});
	sort(left.begin(), left.end());
	sort(right.begin(), right.end());
	
	int idx = 0;
	for(auto i : right){
		while(idx < left.size() && left[idx].x < i.x){
			bit.update(left[idx].y, left[idx].z); idx++;
		}
		dp[i.z] = max(dp[i.z], bit.query(i.y-1));
	}
	for(int i=0; i<idx; i++) bit.set(v[i].y);
	//right
	solve(m+1, e);
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> m >> n; v.resize(n+1);
	for(int i=1; i<=n; i++) cin >> v[i].x;
	for(int i=1; i<=n; i++) cin >> v[i].y;
	if(m == 3) for(int i=1; i<=n; i++) cin >> v[i].z;
	sort(v.begin()+1, v.end());
	if(m == 2) for(int i=1; i<=n; i++) v[i].z = i;
	
	//decompress
	vector<int> yy, zz;
	for(int i=1; i<=n; i++){
		yy.push_back(v[i].y);
		zz.push_back(v[i].z);
	}
	sort(all(yy));
	sort(all(zz));
	for(int i=1; i<=n; i++){
		v[i].y = lower_bound(all(yy), v[i].y) - yy.begin();
		v[i].z = lower_bound(all(zz), v[i].z) - zz.begin();
	}
	
	solve(1, n);
	
	int ans = 0;
	for(int i=1; i<=n; i++) ans = max(ans, dp[i]);
	cout << ans;
}

Compilation message (stderr)

matrix.cpp: In function 'void solve(int, int)':
matrix.cpp:58:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = s + e >> 1;
          ~~^~~
matrix.cpp:72:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(idx < left.size() && left[idx].x < i.x){
         ~~~~^~~~~~~~~~~~~

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