제출 #1231673

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1231673		MuhammadSaram	나일강 (IOI24_nile)	C++20	38 / 100	101 ms	22068 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define all(v) v.begin(), v.end()

const int M = 1e5 + 1, inf = 1e9 + 1;

int w[M], a[M], b[M], col[M], sz[M], mn[M][4];
ll su[M];
vector<int> ver[M];

void add(int u,int v)
{
	u=col[u], v=col[v];
	if (u==v) return;
	if (sz[u]<sz[v]) swap(u,v);
	for (int i:ver[v])
		col[i]=u, ver[u].push_back(i);
	ver[v].clear();
	sz[u]+=sz[v],su[u]+=su[v];
	for (int j=0;j<4;j++)
		mn[u][j]=min(mn[u][j],mn[v][j]);
}

ll cal(int i)
{
	i=col[i];
	return su[i]+min(mn[i][mn[i][3]%2],mn[i][2])*(sz[i]%2);
}

vector<ll> calculate_costs(vector<int> W, vector<int> A, 
vector<int> B, vector<int> E)
{
	int n=W.size(), q=E.size();
	vector<pair<int,int>> v,v1;
	for (int i=0;i<n;i++)
		v.push_back({W[i],i});
	for (int i=0;i<q;i++)
		v1.push_back({E[i],i});
	sort(all(v)), sort(all(v1));
	vector<pair<int,pair<int,int>>> edg;
	ll cur=0;
	vector<ll> ans(q);
	for (int i=0;i<n;i++)
	{
		w[i]=v[i].first,b[i]=B[v[i].second],a[i]=A[v[i].second]-b[i];
		if (i) edg.push_back({w[i]-w[i-1],{i-1,i}});
		if (i>1) edg.push_back({w[i]-w[i-2],{i-2,i}});
		col[i]=mn[i][3]=i,sz[i]=1,ver[i]={i},su[i]=b[i];
		mn[i][0]=mn[i][1]=mn[i][2]=inf;
		mn[i][i%2]=a[i];
		cur+=cal(i);
	}
	sort(all(edg));
	int id=0;
	for (int i=0;i<q;i++)
	{
		int x=v1[i].first;
		while (id<edg.size() && edg[id].first<=x)
		{
			pair<int,int> ed=edg[id++].second;
			if (ed.first==ed.second-1)
			{
				cur-=cal(ed.first)+cal(ed.second);
				add(ed.first,ed.second);
				cur+=cal(ed.first);
			}
			else
			{
				cur-=cal(ed.first);
				mn[i][2]=min(mn[i][2],a[ed.first+1]);
				cur+=cal(ed.first);
			}
		}
		ans[v1[i].second]=cur;
	}
	return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 0 / 13
• Subtask 3: 17 / 17
• Subtask 4: 0 / 11
• Subtask 5: 0 / 20
• Subtask 6: 15 / 15
• Subtask 7: 0 / 18