oj.uz

Submission #843334

# Submission time Handle Problem Language Result Execution time Memory
843334 2023-09-03T23:09:44 Z pera Colouring a rectangle (eJOI19_colouring) C++17
30 / 100
 1 ms 860 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 1e3;
vector<int> t(4 * N) , lz(4 * N);

void push(int u){
	t[u * 2] += lz[u];
	t[u * 2 + 1] += lz[u];
	lz[u * 2] += lz[u];
	lz[u * 2 + 1] += lz[u];
	lz[u] = 0;
}

void make_new(int n){
	function<void(int , int , int)> build = [&](int u , int l , int r){
		lz[u] = t[u] = 0;
		if(l == r) return;
		int m = (l + r) / 2;
		build(u * 2 , l , m);
		build(u * 2 + 1 , m + 1 , r);
	};
	build(n , 0 , n);
}
void pos_assign(int u , int l , int r , int pos , int val){
	if(l == r){
		t[u] = val;
		return;
	}
	push(u);
	int m = (l + r) / 2;
	if(pos <= m) pos_assign(u * 2 , l , m , pos , val);
	else pos_assign(u * 2 + 1 , m + 1 , r , pos , val);
	t[u] = max(t[u * 2] , t[u * 2 + 1]);
}
void range_add(int u , int l , int r , int L , int R , int val){
	if(l > r || r < L || l > R) return;
	if(L <= l && r <= R){
		t[u] += val;
		lz[u] += val;
		return;
	}
	push(u);
	int m = (l + r) / 2;
	range_add(u * 2 , l , m , L , R , val);
	range_add(u * 2 + 1 , m + 1 , r , L , R , val);
	t[u] = max(t[u * 2] , t[u * 2 + 1]);
}

int get_max(int u , int l , int r , int L , int R){
	if(l > r || r < L || l > R) return 0;
	if(L <= l && r <= R) return t[u];
	push(u);
	int m = (l + r) / 2;
	return max(get_max(u * 2 , l , m , L , R) , get_max(u * 2 + 1 , m + 1 , r , L , R));
}

void pos_assign(int pos , int val , int n){
	if(pos < 0 || n - 1 < pos) return;
	pos_assign(1 , 0 , n , pos , val);
}

void range_add(int l , int r , int val , int n){
	if(r < l) return;
	range_add(1 , 0 , n , l , r , val);
}

int get_max(int l , int r , int n){
	if(r < l) return 0LL;
	return get_max(1 , 0 , n , l , r);
}


main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int n , m;cin >> n >> m;
	vector<int> d1(N) , d2(N) , sz(N); 
	vector<int> f[2];
	vector<vector<vector<pair<int , int>>>> cost(2 , vector<vector<pair<int , int>>>((N)));
	for(int i = 0;i < n + m - 1;i ++){
		cin >> d1[i];
		f[i % 2].push_back(d1[i]);
		if(i < min(n , m)) sz[i] = i + 1;
		if(min(n , m) <= i && i < max(n , m)) sz[i] = sz[i - 1];
		if(i >= max(n , m)) sz[i] = sz[i - 1] - 1;
	}
	int parity;
	for(int i = 0;i < n + m - 1;i ++){
		cin >> d2[i];
		int st = abs(m - i - 1);
		if(i % 2 == 0) parity = st % 2;
		st /= 2;/*
		cout << i << " " << st << "  " << st + sz[i] - 1 << "    " << parity << endl;*/
		cost[i % 2][st + sz[i] - 1].push_back({d2[i] , st});
	}
	int ans = 0;
	for(int w = 0;w < 2;w ++){
		int par = (parity ^ (w == 1)) , all_cost = 0 , N = (int)f[w].size();/*
		cout << "par W: " << w << "    par: " << par << endl; */
		make_new(N);/*
		cout << "SZ: " << N << endl;*/
		for(int i = 0;i < N;i ++){
			int all = get_max(0 , i - 1 , N);
			pos_assign(i , all + f[w][i] , N);
			for(int k = 0;k < cost[par][i].size();k ++){
				int end = cost[par][i][k].second;
				int Cost = -cost[par][i][k].first;
				range_add(end , i , Cost , N);
			}
			all_cost += f[w][i];
		}/*
		cout << "MN: ";
		cout << get_max(0 , N - 1 , N) << endl;*/
		ans += all_cost - max(0LL , get_max(0 , N - 1 , N));
	}
	cout << ans << endl;
}

Compilation message

colouring.cpp:76:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   76 | main(){
      | ^~~~
colouring.cpp: In function 'int main()':
colouring.cpp:108:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |    for(int k = 0;k < cost[par][i].size();k ++){
      |                  ~~^~~~~~~~~~~~~~~~~~~~~
colouring.cpp:101:7: warning: 'parity' may be used uninitialized in this function [-Wmaybe-uninitialized]
  101 |   int par = (parity ^ (w == 1)) , all_cost = 0 , N = (int)f[w].size();/*
      |       ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 600 KB Output is correct
5 Correct 1 ms 856 KB Output is correct
6 Correct 0 ms 600 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 0 ms 600 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 0 ms 600 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 600 KB Output is correct
5 Correct 1 ms 856 KB Output is correct
6 Correct 0 ms 600 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 0 ms 600 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 0 ms 600 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 0 ms 604 KB Output is correct
13 Correct 0 ms 600 KB Output is correct
14 Correct 0 ms 600 KB Output is correct
15 Correct 0 ms 600 KB Output is correct
16 Correct 0 ms 600 KB Output is correct
17 Correct 0 ms 600 KB Output is correct
18 Correct 0 ms 600 KB Output is correct
19 Correct 0 ms 600 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 600 KB Output is correct
5 Correct 1 ms 856 KB Output is correct
6 Correct 0 ms 600 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 0 ms 600 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 0 ms 600 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 0 ms 604 KB Output is correct
13 Correct 0 ms 600 KB Output is correct
14 Correct 0 ms 600 KB Output is correct
15 Correct 0 ms 600 KB Output is correct
16 Correct 0 ms 600 KB Output is correct
17 Correct 0 ms 600 KB Output is correct
18 Correct 0 ms 600 KB Output is correct
19 Correct 0 ms 600 KB Output is correct
20 Correct 1 ms 600 KB Output is correct
21 Correct 1 ms 740 KB Output is correct
22 Correct 0 ms 604 KB Output is correct
23 Correct 0 ms 516 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 0 ms 604 KB Output is correct
26 Correct 0 ms 604 KB Output is correct
27 Correct 0 ms 604 KB Output is correct
28 Correct 1 ms 604 KB Output is correct
29 Correct 1 ms 604 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 600 KB Output is correct
5 Correct 1 ms 856 KB Output is correct
6 Correct 0 ms 600 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 0 ms 600 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 0 ms 600 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 0 ms 604 KB Output is correct
13 Correct 0 ms 600 KB Output is correct
14 Correct 0 ms 600 KB Output is correct
15 Correct 0 ms 600 KB Output is correct
16 Correct 0 ms 600 KB Output is correct
17 Correct 0 ms 600 KB Output is correct
18 Correct 0 ms 600 KB Output is correct
19 Correct 0 ms 600 KB Output is correct
20 Correct 1 ms 600 KB Output is correct
21 Correct 1 ms 740 KB Output is correct
22 Correct 0 ms 604 KB Output is correct
23 Correct 0 ms 516 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 0 ms 604 KB Output is correct
26 Correct 0 ms 604 KB Output is correct
27 Correct 0 ms 604 KB Output is correct
28 Correct 1 ms 604 KB Output is correct
29 Correct 1 ms 604 KB Output is correct
30 Runtime error 1 ms 860 KB Execution killed with signal 6
31 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 856 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 856 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 600 KB Output is correct
5 Correct 1 ms 856 KB Output is correct
6 Correct 0 ms 600 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 0 ms 600 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 0 ms 600 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 0 ms 604 KB Output is correct
13 Correct 0 ms 600 KB Output is correct
14 Correct 0 ms 600 KB Output is correct
15 Correct 0 ms 600 KB Output is correct
16 Correct 0 ms 600 KB Output is correct
17 Correct 0 ms 600 KB Output is correct
18 Correct 0 ms 600 KB Output is correct
19 Correct 0 ms 600 KB Output is correct
20 Correct 1 ms 600 KB Output is correct
21 Correct 1 ms 740 KB Output is correct
22 Correct 0 ms 604 KB Output is correct
23 Correct 0 ms 516 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 0 ms 604 KB Output is correct
26 Correct 0 ms 604 KB Output is correct
27 Correct 0 ms 604 KB Output is correct
28 Correct 1 ms 604 KB Output is correct
29 Correct 1 ms 604 KB Output is correct
30 Runtime error 1 ms 860 KB Execution killed with signal 6
31 Halted 0 ms 0 KB -