oj.uz

Submission #64204

# Submission time Handle Problem Language Result Execution time Memory
64204 2018-08-03T13:38:31 Z gs14004 None (KOI18_matrix) C++17
100 / 100
 1016 ms 85672 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <bitset>
#include <iostream>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int MAXN = 300005;
const int mod = 1e9 + 7;

struct tup{
	int x, y, z;
	bool operator<(const tup &t)const{
		return x < t.x;
	}
}a[MAXN];

struct bit{
	int tree[MAXN];
	void add(int x, int v){
		x++;
		while(x < MAXN){
			tree[x] = max(tree[x], v);
			x += x & -x;
		}
	}
	void flush(int x){
		x++;
		while(x < MAXN){
			tree[x] = 0;
			x += x & -x;
		}
	}
	int query(int x){
		x++;
		int ret = 0;
		while(x){
			ret = max(ret, tree[x]);
			x -= x & -x;
		}
		return ret;
	}
}bit;

int dp[MAXN];

void solve(int s, int e){
	if(s == e){
		dp[s]++;
		return;
	}
	int m = (s+e)/2;
	solve(s, m);
	vector<tup> v, w;
	for(int i=s; i<=m; i++) v.push_back((tup){a[i].y, a[i].z, dp[i]});
	for(int i=m+1; i<=e; i++) w.push_back((tup){a[i].y, a[i].z, i});
	int ptr = 0;
	sort(v.begin(), v.end());
	sort(w.begin(), w.end());
	for(auto &i : w){
		while(ptr < v.size() && v[ptr].x < i.x){
			bit.add(v[ptr].y, v[ptr].z);
			ptr++;
		}
		dp[i.z] = max(dp[i.z], bit.query(i.y - 1));
	}
	for(int i=0; i<ptr; i++) bit.flush(v[i].y);
	solve(m + 1, e);
}

int main(){
	int m, n;
	scanf("%d %d",&m,&n);
	for(int i=0; i<n; i++) scanf("%d",&a[i].x);
	for(int i=0; i<n; i++) scanf("%d",&a[i].y);
	if(m == 3) for(int i=0; i<n; i++) scanf("%d",&a[i].z);
	sort(a, a+n);
	if(m == 2) for(int i=0; i<n; i++) a[i].z = i;
	vector<int> vy, vz;
	for(int i=0; i<n; i++){
		vy.push_back(a[i].y);
		vz.push_back(a[i].z);
	}
	sort(vy.begin(), vy.end());
	sort(vz.begin(), vz.end());
	for(int i=0; i<n; i++){
		int yv = lower_bound(vy.begin(), vy.end(), a[i].y) - vy.begin();
		int zv = lower_bound(vz.begin(), vz.end(), a[i].z) - vz.begin();
		a[i].y = yv;
		a[i].z = zv;
	}
	solve(0, n-1);
	cout << *max_element(dp, dp + n) << endl;
}

Compilation message

matrix.cpp: In function 'void solve(int, int)':
matrix.cpp:75:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ptr < v.size() && v[ptr].x < i.x){
         ~~~~^~~~~~~~~~
matrix.cpp: In function 'int main()':
matrix.cpp:87: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:88:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<n; i++) scanf("%d",&a[i].x);
                         ~~~~~^~~~~~~~~~~~~~
matrix.cpp:89:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<n; i++) scanf("%d",&a[i].y);
                         ~~~~~^~~~~~~~~~~~~~
matrix.cpp:90:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  if(m == 3) for(int i=0; i<n; i++) scanf("%d",&a[i].z);
                                    ~~~~~^~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1272 KB Output is correct
2 Correct 30 ms 1372 KB Output is correct
3 Correct 31 ms 1588 KB Output is correct
4 Correct 30 ms 1812 KB Output is correct
5 Correct 34 ms 2020 KB Output is correct
6 Correct 27 ms 2280 KB Output is correct
7 Correct 29 ms 2476 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2828 KB Output is correct
2 Correct 39 ms 3108 KB Output is correct
3 Correct 42 ms 3296 KB Output is correct
4 Correct 40 ms 3816 KB Output is correct
5 Correct 40 ms 4028 KB Output is correct
6 Correct 32 ms 4320 KB Output is correct
7 Correct 42 ms 4612 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1272 KB Output is correct
2 Correct 30 ms 1372 KB Output is correct
3 Correct 31 ms 1588 KB Output is correct
4 Correct 30 ms 1812 KB Output is correct
5 Correct 34 ms 2020 KB Output is correct
6 Correct 27 ms 2280 KB Output is correct
7 Correct 29 ms 2476 KB Output is correct
8 Correct 822 ms 18272 KB Output is correct
9 Correct 757 ms 22152 KB Output is correct
10 Correct 665 ms 25700 KB Output is correct
11 Correct 400 ms 25700 KB Output is correct
12 Correct 760 ms 25872 KB Output is correct
13 Correct 574 ms 25872 KB Output is correct
14 Correct 686 ms 25872 KB Output is correct
15 Correct 375 ms 25872 KB Output is correct
16 Correct 565 ms 25872 KB Output is correct
17 Correct 522 ms 25872 KB Output is correct
18 Correct 622 ms 25872 KB Output is correct
19 Correct 706 ms 25872 KB Output is correct
20 Correct 811 ms 25872 KB Output is correct

Subtask #4
62.0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2828 KB Output is correct
2 Correct 39 ms 3108 KB Output is correct
3 Correct 42 ms 3296 KB Output is correct
4 Correct 40 ms 3816 KB Output is correct
5 Correct 40 ms 4028 KB Output is correct
6 Correct 32 ms 4320 KB Output is correct
7 Correct 42 ms 4612 KB Output is correct
8 Correct 759 ms 31628 KB Output is correct
9 Correct 772 ms 37072 KB Output is correct
10 Correct 669 ms 43088 KB Output is correct
11 Correct 619 ms 48940 KB Output is correct
12 Correct 577 ms 53896 KB Output is correct
13 Correct 807 ms 60444 KB Output is correct
14 Correct 796 ms 66456 KB Output is correct
15 Correct 677 ms 72048 KB Output is correct
16 Correct 622 ms 77876 KB Output is correct
17 Correct 766 ms 83492 KB Output is correct
18 Correct 997 ms 85624 KB Output is correct
19 Correct 843 ms 85624 KB Output is correct
20 Correct 807 ms 85624 KB Output is correct
21 Correct 679 ms 85624 KB Output is correct
22 Correct 1016 ms 85624 KB Output is correct
23 Correct 808 ms 85624 KB Output is correct
24 Correct 795 ms 85624 KB Output is correct
25 Correct 858 ms 85672 KB Output is correct
26 Correct 836 ms 85672 KB Output is correct
27 Correct 513 ms 85672 KB Output is correct
28 Correct 661 ms 85672 KB Output is correct
29 Correct 727 ms 85672 KB Output is correct
30 Correct 619 ms 85672 KB Output is correct
31 Correct 899 ms 85672 KB Output is correct
32 Correct 650 ms 85672 KB Output is correct