Submission #390057

#	Time	Username	Problem	Language	Result	Execution time	Memory
390057		alireza_kaviani	Wiring (IOI17_wiring)	C++11	13 / 100	234 ms	15228 KiB

wiring

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

typedef long long ll;
typedef pair<int, int> pii;

#define sep			' '
#define X			first
#define Y			second
#define lc			id << 1
#define rc			lc | 1
#define all(x)		(x).begin() , (x).end()
#define SZ(x)		int((x).size())

const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;
const ll INF = 1e18;

ll dp[MAXN] , seg[2][MAXN << 2];

void modify(int ind , int x , ll val , int id = 1 , int l = 0 , int r = MAXN){
	if(r - l == 1){
		seg[ind][id] = val;
		return;
	}
	int mid = l + r >> 1;
	if(x < mid)	modify(ind , x , val , lc , l , mid);
	else	modify(ind , x , val , rc , mid , r);
	seg[ind][id] = min(seg[ind][lc] , seg[ind][rc]);
}

ll get(int ind , int ql , int qr , int id = 1 , int l = 0 , int r = MAXN){
	if(qr <= l || r <= ql)	return INF;
	if(ql <= l && r <= qr)	return seg[ind][id];
	int mid = l + r >> 1;
	return min(get(ind , ql , qr , lc , l , mid) , get(ind , ql , qr , rc , mid , r));
}

ll min_total_length(vector<int> r, vector<int> b) {
	vector<pii> compress = {{-1 , 0} , {MOD , 0}};
	int n = SZ(r) + SZ(b);
	for(int i : r)	compress.push_back({i , 0});
	for(int i : b)	compress.push_back({i , 1});
	sort(all(compress));
	dp[n] = 0;
	int x = n , y = -1;
	ll v = 0 , u = 0;
//	for(int i = 0 ; i < SZ(compress) ; i++){
//		cout << i << sep << compress[i].X << sep << compress[i].Y << endl;
//	}
	for(int i = n - 1 ; i >= 0 ; i--){
		if(y == -1)	dp[i] = INF;
		else{
			v += compress[x + 1].X - compress[i + 1].X;
			u += compress[x].X - compress[i + 1].X;
			dp[i] = min(get(0 , x + 1 , min(y + 1 , 2 * x - i + 1)) + v , get(1 , 2 * x - i + 1 , y + 1) + u);
		}
//		cout << i << sep << dp[i] << endl;
		if(i > 0 && compress[i].Y != compress[i + 1].Y){
			y = x; x = i; v = 0 , u = 0;
			ll A = 0 , B = 0;
			for(int j = i + 1 ; j <= y ; j++){
				A += compress[j].X - compress[x + 1].X;
				B += compress[j].X - compress[x].X;
				modify(0 , j , dp[j] + A);
				modify(1 , j , dp[j] + B);
			}
			continue;
		}
	}
	return dp[0];
}

Compilation message (stderr)

wiring.cpp: In function 'void modify(int, int, ll, int, int, int)':
wiring.cpp:27:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |  int mid = l + r >> 1;
      |            ~~^~~
wiring.cpp: In function 'll get(int, int, int, int, int, int)':
wiring.cpp:36:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |  int mid = l + r >> 1;
      |            ~~^~~

• Subtask 1: 0 / 7
• Subtask 2: 13 / 13
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45