oj.uz

Submission #34680

# Submission time Handle Problem Language Result Execution time Memory
34680 2017-11-15T01:22:12 Z mohammad_kilani Wiring (IOI17_wiring) C++14
13 / 100
 263 ms 21588 KB 
#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
#define red 1
#define blue 0
const int N = 200010;

long long seg[4 * N] , lazy[4 * N] , dp[N];
vector< pair<int,bool> > v;
int n , nxt[N];

long long getmin(int s,int e,int idx,int l,int r){
	if(s > r || e < l) return 1e18;
	if(s >= l && e <= r) return seg[idx] + lazy[idx];
	lazy[idx*2] += lazy[idx];
	lazy[idx*2+1] += lazy[idx];
	seg[idx] += lazy[idx];
	lazy[idx] = 0;
	return min(getmin(s,(s+e)/2,idx*2,l,r),getmin((s+e)/2+1,e,idx*2+1,l,r));
}

long long update(int s,int e,int idx,int l,int r,long long val){
	if(s > r || e < l) return seg[idx] + lazy[idx];
	if(s >= l && e <= r){
		lazy[idx] += val;
		return seg[idx] + lazy[idx];
	}
	lazy[idx*2] += lazy[idx];
	lazy[idx*2+1] += lazy[idx];
	lazy[idx] =0 ;
	return seg[idx] = min(update(s,(s+e)/2,idx*2,l,r,val),update((s+e)/2+1,e,idx*2+1,l,r,val));
}


long long min_total_length(std::vector<int> r, std::vector<int> b) {
	int j =0 ;
	for(int i=0;i<r.size();i++){
		while(j < b.size() && b[j] < r[i]) v.push_back(make_pair(b[j++],blue));
		v.push_back(make_pair(r[i],red));
	}
	while(j < b.size()) v.push_back(make_pair(b[j++],blue));
	n = v.size();
	nxt[n] = n;
	for(int i=n-1;i>=0;i--){
		if(v[i].second != v[i+1].second) nxt[i] = i + 1; else nxt[i] = nxt[i+1];
	}
	for(int i=n-1;i>=0;i--){
		if(nxt[i] == n){
			dp[i] = 1e18;
			update(0,n,1,i,i,dp[i]);
			continue;
		}
		dp[i] = 1e18;
		if(nxt[i] == i + 1){
			long long sum = 0 ;
			for(int j=i+1;j<nxt[i+1];j++){
				update(0,n,1,j,j,sum);
				sum += v[j].first - v[i].first;
			}
			for(int j=nxt[i+1];j<=nxt[nxt[i+1]];j++){
				update(0,n,1,j,j,-getmin(0,n,1,j,j));
				update(0,n,1,j,j,dp[j] + sum);
				if(j < nxt[nxt[i+1]]) sum += v[j].first - v[i+1].first;
			}
			dp[i] = min(dp[i],getmin(0,n,1,i+2,nxt[nxt[i+1]]));
			update(0,n-1,1,i,i,dp[i]);
		}
		else{
			int cur = nxt[i] ; 
			int cur2 = nxt[cur] - 1;
			int num = cur - i;
			long long s = 0 ;
			if(cur2 - cur < num){
				if(cur+1 <= cur2) update(0,n,1,cur+1,cur2,v[cur].first - v[i].first);
			}
			else{
				update(0,n,1,cur+1,cur+num-1,v[cur].first-v[i].first);
				if(cur+num <= cur2){
					update(0,n,1,cur+num,cur2,v[cur-1].first - v[i].first);
				}
			}
			cur2++;
			if(cur2 - cur < num) s = v[cur].first - v[i].first;
			else s = v[cur-1].first - v[i].first;
			update(0,n,1,cur2,nxt[cur2],s);
			dp[i] = getmin(0,n,1,cur+1,nxt[cur2]);
			update(0,n,1,i,i,dp[i]);
		}

	}
	return dp[0];

}

Compilation message

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:37:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<r.size();i++){
               ^
wiring.cpp:38:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(j < b.size() && b[j] < r[i]) v.push_back(make_pair(b[j++],blue));
           ^
wiring.cpp:41:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(j < b.size()) v.push_back(make_pair(b[j++],blue));
          ^

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 16864 KB 3rd lines differ - on the 1st token, expected: '25859', found: '19727'
2 Halted 0 ms 0 KB -

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 16864 KB Output is correct
2 Correct 0 ms 16864 KB Output is correct
3 Correct 189 ms 21196 KB Output is correct
4 Correct 199 ms 21196 KB Output is correct
5 Correct 166 ms 21196 KB Output is correct
6 Correct 263 ms 21588 KB Output is correct
7 Correct 253 ms 21588 KB Output is correct
8 Correct 233 ms 21588 KB Output is correct
9 Correct 219 ms 21588 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 16864 KB Output is correct
2 Incorrect 0 ms 16864 KB 3rd lines differ - on the 1st token, expected: '17703', found: '922'
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 16864 KB 3rd lines differ - on the 1st token, expected: '27', found: '13'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 16864 KB 3rd lines differ - on the 1st token, expected: '25859', found: '19727'
2 Halted 0 ms 0 KB -