제출 #1312227

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1312227		exoworldgd	나일강 (IOI24_nile)	C++20	0 / 100	64 ms	12528 KiB

nile

#include "nile.h"
#include<bits/stdc++.h>
#define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0)
#define ll long long
using namespace std;
const int INF=1e9;
vector<ll>calculate_costs(vector<int>W,vector<int>A,vector<int>B,vector<int>E){
	int n=W.size(),q=E.size();
	vector<int>ordW(n),ordE(q),w(n),c(n),len(n);
	iota(ordW.begin(),ordW.end(),0),iota(ordE.begin(),ordE.end(),0),sort(ordW.begin(),ordW.end(),[&](int i,int j){return W[i]<W[j];}),sort(ordE.begin(),ordE.end(),[&](int i,int j){return E[i]<E[j];});
	for(int i=0;i<n;i++)w[i]=W[ordW[i]],c[i]=A[ordW[i]]-B[ordW[i]];
	vector<array<int,3>>e,mnc(n);
	for(int i=0;i<n;i++){
		if(i+1<n)e.push_back({w[i+1]-w[i],i,1});
		if(i+2<n)e.push_back({w[i+2]-w[i],i,0});
	}
	sort(e.rbegin(),e.rend());
	set<int>s;
	ll sum=0;
	for(int i=0;i<n;i++)s.insert(i),len[i]=1,mnc[i]={INF,INF,INF},mnc[i][i&1]=c[i],sum+=c[i];
	auto cost=[&](int i){return mnc[i][mnc[i][i&1]<mnc[i][2]?i&1:2]*(len[i]&1);};
	auto mrg=[&](int i){
		int j=*prev(s.upper_bound(i)),k=i+1;
		sum-=cost(j),sum-=cost(k),s.erase(k),len[j]+=len[k];
		for(int p=0;p<3;p++)mnc[j][p]=min(mnc[j][p],mnc[k][p]);
		sum+=cost(j);
	};
	auto upd=[&](int i){
		int j=*prev(s.upper_bound(i));
		sum-=cost(j),mnc[j][2]=min(mnc[j][2],c[i]),sum+=cost(j);
	};
	vector<ll>R(q,accumulate(B.begin(),B.end(),0ll));
	for(int i=0;i<q;i++){
		while(e.size()&&e.back()[0]<=E[ordE[i]]){auto[u,v,x]=e.back();e.pop_back(),x?(mrg(u),0):(upd(u+1),0);}
		R[ordE[i]]+=sum;
	}
	return R;
}

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