Submission #399824

#	Time	Username	Problem	Language	Result	Execution time	Memory
399824		Husayn	전선 연결 (IOI17_wiring)	C++14	0 / 100	1 ms	304 KiB

wiring

#include "wiring.h"
#include "bits/stdc++.h"
#define MAXN 200009
#define MOD 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
#define vi vector <int>

using namespace std;

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

template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}

ll f[MAXN*4],lazy[MAXN*4],n,dp[MAXN];
vector<PII> point;

void push(int nd,int l,int r) {
	f[nd] += lazy[nd];
	if(l != r) {
		lazy[nd >> 1] += lazy[nd];
		lazy[nd >> 1 | 1] += lazy[nd];
	}
	lazy[nd] = 0;
}

void upd(int nd,int l,int r,int x,int y,ll val) {

	if(lazy[nd]!=0)
		push(nd,l,r);

	if(l > y or r < x)
		return;
	if(l >= x and r <= y) {
		lazy[nd]=val;
		push(nd,l,r);
		return;
	}

	int md=(l+r)/2;
	upd(nd >> 1,l,md, x, y,val);
	upd(nd >> 1 | 1,md+1,r, x, y,val);
	f[nd]=min(f[nd >> 1],f[nd >> 1 | 1]);
}
ll que(int nd,int l,int r,int x,int y) {

	if(lazy[nd]!=0)
		push(nd,l,r);

	if(l > y or r < x)
		return 1e17;
	if(l >= x and r <= y)
		return f[nd];

	int md=(l+r)/2;
	return min(que(nd >> 1,l,md,x,y),que(nd >> 1 | 1, md+1, r, x, y));

}
long long min_total_length(std::vector<int> rx, std::vector<int> b) {
	
	n=rx.size()+b.size();

	for(int i=0;i<rx.size();++i)
		point.pb(mp(rx[i],0));
	for(int i=0;i<b.size();++i)
		point.pb(mp(b[i],1));

	sort(point.begin(),point.end());

	dp[n]=0; //dp[i] minimal uzunlikdagi bog`langan nuqtalarni saqlaydi i, i+1, ... n-1
	dp[n-1]=1e17;

	int l=n,r,fr=n-1;

	for(int i=n-2;i>=0;--i) {

		if(point[i].ss!=point[i+1].ss) {
			r=fr;
			l=i+1;
			fr=i;
			ll sum = 0ll;
			for(int j=l;j<=r;++j) {
				sum+=point[j].ff;
				upd(1,0,n-1,j,j,min(dp[j],dp[j+1])+sum-point[i].ff*(j-l+1));
			}
		}
		else if(l!=n) {
			upd(1,0,n-1,l,min(r,l+(fr-i-1)),point[l].ff-point[i].ff);
			if(l+fr-i<=r)
				upd(1,0,n-1,l+fr-i,r,point[fr].ff-point[i].ff);
		}

		if(l!=n) dp[i]=que(1,0,n-1,l,r);
		else dp[i]=1e17;
		//cout<<i<<" "<<dp[i]<<endl;

	} 

	return dp[0];

}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:73:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |  for(int i=0;i<rx.size();++i)
      |              ~^~~~~~~~~~
wiring.cpp:75:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |  for(int i=0;i<b.size();++i)
      |              ~^~~~~~~~~
wiring.cpp:100:8: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
  100 |     upd(1,0,n-1,l+fr-i,r,point[fr].ff-point[i].ff);
      |     ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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