oj.uz

Submission #63149

# Submission time Handle Problem Language Result Execution time Memory
63149 2018-08-01T01:14:09 Z khsoo01 None (KOI18_matrix) C++11
100 / 100
 506 ms 152972 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 23 ms 10516 KB Output is correct
2 Correct 21 ms 10988 KB Output is correct
3 Correct 26 ms 10988 KB Output is correct
4 Correct 26 ms 11332 KB Output is correct
5 Correct 23 ms 11440 KB Output is correct
6 Correct 21 ms 11772 KB Output is correct
7 Correct 25 ms 11876 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 11876 KB Output is correct
2 Correct 24 ms 12224 KB Output is correct
3 Correct 26 ms 12264 KB Output is correct
4 Correct 24 ms 12560 KB Output is correct
5 Correct 22 ms 12916 KB Output is correct
6 Correct 21 ms 13528 KB Output is correct
7 Correct 26 ms 13528 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 10516 KB Output is correct
2 Correct 21 ms 10988 KB Output is correct
3 Correct 26 ms 10988 KB Output is correct
4 Correct 26 ms 11332 KB Output is correct
5 Correct 23 ms 11440 KB Output is correct
6 Correct 21 ms 11772 KB Output is correct
7 Correct 25 ms 11876 KB Output is correct
8 Correct 483 ms 30280 KB Output is correct
9 Correct 401 ms 33780 KB Output is correct
10 Correct 169 ms 33904 KB Output is correct
11 Correct 304 ms 34008 KB Output is correct
12 Correct 230 ms 34008 KB Output is correct
13 Correct 170 ms 34008 KB Output is correct
14 Correct 221 ms 34008 KB Output is correct
15 Correct 322 ms 34008 KB Output is correct
16 Correct 198 ms 34008 KB Output is correct
17 Correct 233 ms 34008 KB Output is correct
18 Correct 170 ms 34008 KB Output is correct
19 Correct 217 ms 34008 KB Output is correct
20 Correct 501 ms 34008 KB Output is correct

Subtask #4
62.0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 11876 KB Output is correct
2 Correct 24 ms 12224 KB Output is correct
3 Correct 26 ms 12264 KB Output is correct
4 Correct 24 ms 12560 KB Output is correct
5 Correct 22 ms 12916 KB Output is correct
6 Correct 21 ms 13528 KB Output is correct
7 Correct 26 ms 13528 KB Output is correct
8 Correct 223 ms 35360 KB Output is correct
9 Correct 246 ms 36172 KB Output is correct
10 Correct 207 ms 40104 KB Output is correct
11 Correct 206 ms 42468 KB Output is correct
12 Correct 180 ms 42468 KB Output is correct
13 Correct 248 ms 44296 KB Output is correct
14 Correct 360 ms 47064 KB Output is correct
15 Correct 198 ms 56780 KB Output is correct
16 Correct 204 ms 62644 KB Output is correct
17 Correct 305 ms 65292 KB Output is correct
18 Correct 382 ms 68844 KB Output is correct
19 Correct 190 ms 74652 KB Output is correct
20 Correct 251 ms 82736 KB Output is correct
21 Correct 200 ms 91780 KB Output is correct
22 Correct 357 ms 92176 KB Output is correct
23 Correct 296 ms 100208 KB Output is correct
24 Correct 199 ms 103752 KB Output is correct
25 Correct 309 ms 110180 KB Output is correct
26 Correct 506 ms 124052 KB Output is correct
27 Correct 215 ms 124052 KB Output is correct
28 Correct 225 ms 132396 KB Output is correct
29 Correct 279 ms 135020 KB Output is correct
30 Correct 274 ms 140896 KB Output is correct
31 Correct 452 ms 152972 KB Output is correct
32 Correct 276 ms 152972 KB Output is correct