Submission #835177

#	Time	Username	Problem	Language	Result	Execution time	Memory
835177		tolbi	Meetings (IOI18_meetings)	C++17	19 / 100	5525 ms	12256 KiB

meetings

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define tol(bi) (1LL<<((ll)(bi)))
#include "meetings.h"
#define INF LONG_LONG_MAX
struct SegTree{
	vector<ll> segtree;
	vector<ll> lazy;
	SegTree(int n){
		segtree.resize(tol(ceil(log2(n)+1))-1,0);
		lazy.resize(segtree.size(), 0ll);
	}
	void dallan(int node){
		segtree[node]+=lazy[node];
		if (node*2+1<segtree.size()){
			lazy[node*2+1]+=lazy[node];
			lazy[node*2+2]+=lazy[node];
		}
		lazy[node]=0;
	}
	void update(int tarl, int tarr, ll val, int l = 0, int r = -1, int node = 0){
		if (r==-1) r = segtree.size()/2;
		dallan(node);
		if (l>=tarl && r<=tarr){
			lazy[node]+=val;
			dallan(node);
			return;
		}
		if (l>tarr || r<tarl) return;
		int mid = l+(r-l)/2;
		update(tarl, tarr, val, l, mid, node*2+1);
		update(tarl, tarr, val, mid+1, r, node*2+2);
		segtree[node]=min(segtree[node*2+1],segtree[node*2+2]);
	}
	ll query(int tarl, int tarr, int l = 0, int r = -1, int node = 0){
		if (r==-1) r = segtree.size()/2;
		dallan(node);
		if (l>=tarl && r<=tarr) return segtree[node];
		if (l>tarr || r<tarl) return INF;
		int mid = l+(r-l)/2;
		ll lnode = query(tarl, tarr, l, mid, node*2+1);
		ll rnode = query(tarl, tarr, mid+1, r, node*2+2);
		return min(lnode,rnode);
	}
};
vector<long long> minimum_costs(vector<int> arr, vector<int> L, vector<int> R) {
	ll q = L.size();
	ll n = arr.size();
	vector<ll> ansarr(q,0);
	SegTree segtree(n);
	vector<ll> leftdp(n);
	vector<ll> rightdp(n);
	vector<ll> sonra(n,n);
	vector<ll> once(n,-1);
	vector<ll> stak;
	for (ll i = 0; i < n; i++){
		while (stak.size() && arr[stak.back()]<=arr[i]){
			stak.pop_back();
		};
		if (stak.size()==0){
			leftdp[i]=(i+1)*arr[i];
		}
		else {
			once[i]=stak.back();
			leftdp[i]=leftdp[stak.back()]+arr[i]*(i-stak.back());
		}
		stak.push_back(i);
	}
	stak.clear();
	for (ll i = n-1; i >= 0; i--){
		while (stak.size() && arr[stak.back()]<=arr[i]){
			stak.pop_back();
		}
		if (stak.size()==0){
			rightdp[i]=(n-1-i+1)*arr[i];
		}
		else {
			sonra[i]=stak.back();
			rightdp[i]=rightdp[stak.back()]+arr[i]*(stak.back()-i);
		}
		stak.push_back(i);
	}
	for (ll i = 0; i < n; i++){
		segtree.update(i,i,leftdp[i]+rightdp[i]-arr[i]);
	}
	cout<<endl;
	vector<array<int,3>> quarr(q);
	for (int i = 0; i < q; ++i)
	{
		quarr[i]={L[i],R[i],i};
	}
	int BLOK = sqrt(n);
	sort(quarr.begin(), quarr.end(), [&](array<int,3> a, array<int,3> b){
		if (a[0]/BLOK==b[0]/BLOK) return a[1]<b[1];
		return a[0]<b[0];
	});
	int lastl = 0;
	int lastr = n-1;
	for (int i = 0; i < quarr.size(); i++){
		int l = quarr[i][0];
		int r = quarr[i][1];
		while (lastl>l){
			int node = lastl-1;
			while (node<n){
				segtree.update(node,sonra[node]-1,arr[node]);
				node=sonra[node];
			}
			lastl--;
		}
		while (lastr<r){
			int node = lastr+1;
			while (node>=0){
				segtree.update(once[node]+1,node,arr[node]);
				node=once[node];
			}
			lastr++;
		}
		while (lastl<l){
			int node = lastl;
			while (node<n){
				segtree.update(node,sonra[node]-1,-arr[node]);
				node=sonra[node];
			}
			lastl++;
		}
		while (lastr>r){
			int node = lastr;
			while (node>=0){
				segtree.update(once[node]+1,node,-arr[node]);
				node=once[node];
			}
			lastr--;
		}
		ansarr[quarr[i][2]]=segtree.query(l,r);
	}
	return ansarr;
}

Compilation message (stderr)

meetings.cpp: In member function 'void SegTree::dallan(int)':
meetings.cpp:16:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |   if (node*2+1<segtree.size()){
      |       ~~~~~~~~^~~~~~~~~~~~~~~
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:100:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |  for (int i = 0; i < quarr.size(); i++){
      |                  ~~^~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40