oj.uz

Submission #112242

# Submission time Handle Problem Language Result Execution time Memory
112242 2019-05-18T04:34:48 Z jhnah917 None (KOI18_matrix) C++14
29 / 100
 551 ms 14836 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));
	}
	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 21 ms 1152 KB Output is correct
2 Correct 20 ms 1244 KB Output is correct
3 Correct 19 ms 1152 KB Output is correct
4 Correct 18 ms 1152 KB Output is correct
5 Correct 21 ms 1144 KB Output is correct
6 Correct 16 ms 1152 KB Output is correct
7 Correct 17 ms 1152 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 1280 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 21 ms 1152 KB Output is correct
2 Correct 20 ms 1244 KB Output is correct
3 Correct 19 ms 1152 KB Output is correct
4 Correct 18 ms 1152 KB Output is correct
5 Correct 21 ms 1144 KB Output is correct
6 Correct 16 ms 1152 KB Output is correct
7 Correct 17 ms 1152 KB Output is correct
8 Correct 546 ms 14760 KB Output is correct
9 Correct 508 ms 14612 KB Output is correct
10 Correct 396 ms 14748 KB Output is correct
11 Correct 221 ms 13848 KB Output is correct
12 Correct 456 ms 14712 KB Output is correct
13 Correct 324 ms 14580 KB Output is correct
14 Correct 443 ms 14764 KB Output is correct
15 Correct 236 ms 13840 KB Output is correct
16 Correct 307 ms 14636 KB Output is correct
17 Correct 301 ms 14836 KB Output is correct
18 Correct 392 ms 14744 KB Output is correct
19 Correct 431 ms 14588 KB Output is correct
20 Correct 551 ms 14836 KB Output is correct

Subtask #4
0 / 62.0

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