oj.uz

Submission #843328

# Submission time Handle Problem Language Result Execution time Memory
843328 2023-09-03T23:02:38 Z pera Colouring a rectangle (eJOI19_colouring) C++17
0 / 100
 2000 ms 102400 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 1e6;
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 - 1);
}
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){
	pos_assign(1 , 0 , n - 1 , pos , val);
}

void range_add(int l , int r , int val , int n){
	range_add(1 , 0 , n - 1 , l , r , val);
}

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


main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int n , m;cin >> n >> m;
	vector<int> d1(n + m - 1) , d2(n + m - 1) , sz(n + m - 1); 
	vector<int> f[2] , fy[2];
	vector<vector<vector<pair<int , int>>>> cost(2 , vector<vector<pair<int , int>>>(n + m));
	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];
		fy[i % 2].push_back(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:74:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   74 | main(){
      | ^~~~
colouring.cpp: In function 'int main()':
colouring.cpp:107: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]
  107 |    for(int k = 0;k < cost[par][i].size();k ++){
      |                  ~~^~~~~~~~~~~~~~~~~~~~~
colouring.cpp:100:7: warning: 'parity' may be used uninitialized in this function [-Wmaybe-uninitialized]
  100 |   int par = (parity ^ (w == 1)) , all_cost = 0 , N = (int)f[w].size();/*
      |       ^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 63064 KB Output is correct
2 Correct 8 ms 63064 KB Output is correct
3 Correct 9 ms 63320 KB Output is correct
4 Correct 8 ms 63068 KB Output is correct
5 Correct 9 ms 63068 KB Output is correct
6 Correct 9 ms 63064 KB Output is correct
7 Correct 8 ms 63068 KB Output is correct
8 Correct 8 ms 63068 KB Output is correct
9 Correct 8 ms 63068 KB Output is correct
10 Execution timed out 2183 ms 102400 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 63064 KB Output is correct
2 Correct 8 ms 63064 KB Output is correct
3 Correct 9 ms 63320 KB Output is correct
4 Correct 8 ms 63068 KB Output is correct
5 Correct 9 ms 63068 KB Output is correct
6 Correct 9 ms 63064 KB Output is correct
7 Correct 8 ms 63068 KB Output is correct
8 Correct 8 ms 63068 KB Output is correct
9 Correct 8 ms 63068 KB Output is correct
10 Execution timed out 2183 ms 102400 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 63064 KB Output is correct
2 Correct 8 ms 63064 KB Output is correct
3 Correct 9 ms 63320 KB Output is correct
4 Correct 8 ms 63068 KB Output is correct
5 Correct 9 ms 63068 KB Output is correct
6 Correct 9 ms 63064 KB Output is correct
7 Correct 8 ms 63068 KB Output is correct
8 Correct 8 ms 63068 KB Output is correct
9 Correct 8 ms 63068 KB Output is correct
10 Execution timed out 2183 ms 102400 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 63064 KB Output is correct
2 Correct 8 ms 63064 KB Output is correct
3 Correct 9 ms 63320 KB Output is correct
4 Correct 8 ms 63068 KB Output is correct
5 Correct 9 ms 63068 KB Output is correct
6 Correct 9 ms 63064 KB Output is correct
7 Correct 8 ms 63068 KB Output is correct
8 Correct 8 ms 63068 KB Output is correct
9 Correct 8 ms 63068 KB Output is correct
10 Execution timed out 2183 ms 102400 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 182 ms 102400 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 80 ms 102400 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 63064 KB Output is correct
2 Correct 8 ms 63064 KB Output is correct
3 Correct 9 ms 63320 KB Output is correct
4 Correct 8 ms 63068 KB Output is correct
5 Correct 9 ms 63068 KB Output is correct
6 Correct 9 ms 63064 KB Output is correct
7 Correct 8 ms 63068 KB Output is correct
8 Correct 8 ms 63068 KB Output is correct
9 Correct 8 ms 63068 KB Output is correct
10 Execution timed out 2183 ms 102400 KB Time limit exceeded
11 Halted 0 ms 0 KB -