Submission #373224

#	Time	Username	Problem	Language	Result	Execution time	Memory
373224		ivan_tudor	Wiring (IOI17_wiring)	C++14	0 / 100	1 ms	384 KiB

wiring

#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 200005;
long long aint[4*N];
long long lazy[4*N];
void propag(int nod,int l, int r){
	aint[nod] += lazy[nod];
	if(l != r){
		lazy[2*nod] += lazy[nod];
		lazy[2*nod + 1] += lazy[nod];
	}
	lazy[nod] = 0;
}
long long computemin(long long a, long long b){
	if(a == 0 && b== 0)
		return 0;
	if(a == 0)
		return b;
	if(b == 0)
		return a;
	return min(a, b);
}
void update(int nod,int l, int r,int ul, int ur, long long val){
	propag(nod, l, r);
	if(l > ur || r < ul || ul > ur)
		return;
	if(ul <= l && r <= ur){
		lazy[nod] += val;
		propag(nod, l, r);
		return;
	}
	int mid = (l + r)/2;
	update(2*nod, l, mid, ul, ur, val);
	update(2*nod + 1, mid+1, r, ul, ur, val);
	aint[nod] = computemin(aint[2*nod], aint[2*nod + 1]);
}
long long query(int nod,int l, int r,int ql, int qr){
	propag(nod, l, r);
	if(l > qr || r < ql || aint[nod] == 0 )
		return LLONG_MAX;
	if(ql <= l && r<= qr){
		return aint[nod];
	}
	int mid = (l + r)/2;
	long long ls = query(2*nod, l, mid, ql, qr);
	long long rs = query(2*nod + 1, mid + 1, r, ql, qr);
	return min(ls, rs);
}
long long dp[N];
struct blocks{
	int t;
	int tip;
};
blocks v[N];
long long min_total_length(std::vector<int> r, std::vector<int> b) {
	int cnt = 0;
	for(int i = 0,j = 0; i < r.size() || j < b.size();){
		if(i == r.size())
			v[++cnt] = {b[j], 2}, j++;
		else if(j == b.size())
			v[++cnt] = {r[i], 1}, i++;
		else if(r[i] < b[j])
		  v[++cnt] = {r[i], 1}, i++;
		else
  		v[++cnt] = {b[j], 2}, j++;
	}
	int n = cnt;
	vector<int> cur, prev;
	cur.push_back(1);
	for(int i=2; i<=n;i++){
		if(v[i].tip == v[i -1].tip){
			cur.push_back(i);
			if(prev.empty())
				continue;
			int lstp = prev[prev.size() - 1], frstp = prev[0];
			long long adg1 = v[i].t - v[lstp].t; // adaugam pe intervalul unde se modifica si la mijloc => nr de b uri devine mai mare ca nr de rosii
			int nrb = cur.size();
			update(1, 1, n, max(frstp, lstp - nrb + 2),lstp, adg1);
			long long adg2 = v[i].t - v[lstp + 1].t;
			update(1, 1, n, frstp, max(frstp, lstp - nrb + 2) - 1, adg2);
		}
		else{
			swap(cur, prev);
			cur.clear();
			cur.push_back(i);
			long long scor = 0;
			for(int j = prev.size() - 1; j >=0; j--){
				scor += v[i].t - v[prev[j]].t;
				long long dpadg = dp[prev[j] - 1];
				if(prev.size() == 1){
					dpadg = min(dp[prev[j]-1], dp[prev[j]]);
				}
				update(1, 1, n, prev[j], prev[j], dpadg + scor);
			}
		}
		int lstp = prev[prev.size() - 1], frstp = prev[0];
		dp[i] = query(1, 1, n, frstp, lstp);
	}
	return dp[n];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:58:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for(int i = 0,j = 0; i < r.size() || j < b.size();){
      |                       ~~^~~~~~~~~~
wiring.cpp:58:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for(int i = 0,j = 0; i < r.size() || j < b.size();){
      |                                       ~~^~~~~~~~~~
wiring.cpp:59:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   if(i == r.size())
      |      ~~^~~~~~~~~~~
wiring.cpp:61:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |   else if(j == b.size())
      |           ~~^~~~~~~~~~~

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