oj.uz

Submission #112243

# Submission time Handle Problem Language Result Execution time Memory
112243 2019-05-18T04:35:43 Z jhnah917 None (KOI18_matrix) C++14
29 / 100
 541 ms 10988 KB 
#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;
	for(int i=1; i<=n; i++){
		if(m == 3) cin >> v[i].z;
		else v[i].z = v[i].y;
	}
	sort(v.begin()+1, v.end());
	
	//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

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
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 896 KB Output is correct
2 Correct 17 ms 1024 KB Output is correct
3 Correct 19 ms 896 KB Output is correct
4 Correct 18 ms 896 KB Output is correct
5 Correct 21 ms 896 KB Output is correct
6 Correct 16 ms 1024 KB Output is correct
7 Correct 17 ms 1024 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 896 KB Output is correct
2 Correct 17 ms 1024 KB Output is correct
3 Correct 19 ms 896 KB Output is correct
4 Correct 18 ms 896 KB Output is correct
5 Correct 21 ms 896 KB Output is correct
6 Correct 16 ms 1024 KB Output is correct
7 Correct 17 ms 1024 KB Output is correct
8 Correct 538 ms 10832 KB Output is correct
9 Correct 504 ms 10796 KB Output is correct
10 Correct 385 ms 10872 KB Output is correct
11 Correct 221 ms 10064 KB Output is correct
12 Correct 466 ms 10808 KB Output is correct
13 Correct 325 ms 10960 KB Output is correct
14 Correct 438 ms 10932 KB Output is correct
15 Correct 228 ms 10032 KB Output is correct
16 Correct 312 ms 10820 KB Output is correct
17 Correct 285 ms 10948 KB Output is correct
18 Correct 357 ms 10944 KB Output is correct
19 Correct 412 ms 10800 KB Output is correct
20 Correct 541 ms 10988 KB Output is correct

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 928 KB Output isn't correct
2 Halted 0 ms 0 KB -