oj.uz

Submission #72923

# Submission time Handle Problem Language Result Execution time Memory
72923 2018-08-27T08:58:54 Z mr_banana Wiring (IOI17_wiring) C++17
13 / 100
 287 ms 18396 KB 
#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
const int MN=2e5+100;
const long long inf=1e15;
long long dp[MN];
long long seg[4*MN],lazy[4*MN];
int bck[MN],fr[MN];
long cbck[MN],cfr[MN];
int n,len,m;
void shift(int v){
	seg[2*v]+=lazy[v];
	lazy[2*v]+=lazy[v];
	seg[2*v+1]+=lazy[v];
	lazy[2*v+1]+=lazy[v];
	lazy[v]=0;
}
void add(int l,int r,long long val,int v=1,int s=0,int e=len+1){
	if(l<=s && e<=r){
		seg[v]+=val;
		lazy[v]+=val;
		return;
	}
	if(l>=e || s>=r){
		return;
	}
	shift(v);
	int mid=(s+e)/2;
	add(l,r,val,2*v,s,mid);
	add(l,r,val,2*v+1,mid,e);
	seg[v]=min(seg[2*v],seg[2*v+1]);
}
long long get(int l,int r,int v=1,int s=0,int e=len+1){
	if(l<=s && e<=r){
		return seg[v];
	}
	if(l>=e || s>=r){
		return inf;
	}
	shift(v);
	int mid=(s+e)/2;
	return min(get(l,r,2*v,s,mid),get(l,r,2*v+1,mid,e));
}
long long min_total_length(vector<int> r, vector<int> b) {
	n=r.size(),m=b.size();
	vector<pair<int,int>> po;
	for(int i:r){
		po.push_back({i,0});
	}
	for(int i:b){
		po.push_back({i,1});
	}
	sort(po.begin(),po.end());
	len=n+m;
	for(int i=0;i<len;i++){
		if(i>0 && po[i-1].second==po[i].second){
			bck[i]=bck[i-1];
			cbck[i]=cbck[i-1]+po[i].first-po[bck[i]].first;
		}
		else{
			bck[i]=i;
			cbck[i]=0;
		}
	}
	for(int i=len-1;i>=0;i--){
		if(i+1<len && po[i+1].second==po[i].second){
			fr[i]=fr[i+1];
			cfr[i]=cfr[i+1]+po[fr[i]].first-po[i].first;
		}
		else{
			fr[i]=i;
			cfr[i]=0;
		}
	}
	dp[0]=0;
	add(0,1,dp[0]+cfr[0]+1ll*(po[fr[0]+1].first-po[fr[0]].first)*(fr[0]+1));
	for(int i=0;i<len;i++){
		int x=bck[i];
		if(x==0){
			dp[i+1]=inf;
		}
		else{
			int y=bck[x-1];
			add(max(2*x-i,y),x,po[x].first-po[x-1].first);
			dp[i+1]=get(y,x)+cbck[i];
		}
		if(fr[i+1]+1<len){
			add(i+1,i+2,dp[i+1]+cfr[i+1]+1ll*(fr[i+1]-i)*(po[fr[i+1]+1].first-po[fr[i+1]].first));
		}
	}
	return dp[len];
}

Subtask #1
0 / 7.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 556 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 97 ms 13288 KB Output is correct
4 Correct 97 ms 13288 KB Output is correct
5 Correct 107 ms 13288 KB Output is correct
6 Correct 135 ms 14208 KB Output is correct
7 Correct 145 ms 14344 KB Output is correct
8 Correct 111 ms 14344 KB Output is correct
9 Correct 129 ms 14344 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14344 KB Output is correct
2 Correct 2 ms 14344 KB Output is correct
3 Incorrect 226 ms 18268 KB 3rd lines differ - on the 1st token, expected: '1068938599', found: '1152497305'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 18268 KB Output is correct
2 Correct 287 ms 18316 KB Output is correct
3 Correct 234 ms 18384 KB Output is correct
4 Correct 240 ms 18384 KB Output is correct
5 Correct 225 ms 18396 KB Output is correct
6 Incorrect 2 ms 18396 KB 3rd lines differ - on the 1st token, expected: '42', found: '43'
7 Halted 0 ms 0 KB -

Subtask #5
0 / 45.0

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