Submission #843338

#	Time	Username	Problem	Language	Result	Execution time	Memory
843338		pera	Colouring a rectangle (eJOI19_colouring)	C++17	100 / 100	407 ms	74780 KiB

colouring

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 4e5;
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){
	for(int i = 0;i <= 4 * n;i ++){
		t[i] = lz[i] = 0;
	}
}
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 (stderr)

colouring.cpp:70:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   70 | main(){
      | ^~~~
colouring.cpp: In function 'int main()':
colouring.cpp:102: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]
  102 |    for(int k = 0;k < cost[par][i].size();k ++){
      |                  ~~^~~~~~~~~~~~~~~~~~~~~
colouring.cpp:95:7: warning: 'parity' may be used uninitialized in this function [-Wmaybe-uninitialized]
   95 |   int par = (parity ^ (w == 1)) , all_cost = 0 , N = (int)f[w].size();/*
      |       ^~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 10 / 10
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20