結果

問題 No.3509 Get More Money
コンテスト
ユーザー Ryan Shaw
提出日時 2026-04-18 00:43:46
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 1,770 ms / 2,000 ms
コード長 6,336 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,369 ms
コンパイル使用メモリ 283,356 KB
実行使用メモリ 113,736 KB
最終ジャッジ日時 2026-04-18 00:44:57
合計ジャッジ時間 69,793 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 60
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'void initcatalan(long long int)':
main.cpp:85:59: warning: iteration 1000002 invokes undefined behavior [-Waggressive-loop-optimizations]
   85 |         for (int i=1; i<CATALANMAX; ++i)cat[i]=(((fact[2*i]*invfact[i])%MOD)*invfact[i+1])%MOD;
      |                                                   ~~~~~~~~^
main.cpp:85:24: note: within this loop
   85 |         for (int i=1; i<CATALANMAX; ++i)cat[i]=(((fact[2*i]*invfact[i])%MOD)*invfact[i+1])%MOD;
      |                       ~^~~~~~~~~~~

ソースコード

diff #
raw source code 

#include <cstdio>
#include <stdio.h>
#include <stdbool.h>
#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
#include <cassert>
#include <random>
#include <chrono>
#include <fstream> 
using namespace std;

#define int long long
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back

const int MOD = 998244353;//
const int FACTMAX = 2000005;//
const int CATALANMAX = 1000005;//

int fact[FACTMAX], invfact[FACTMAX], cat[CATALANMAX];

int expo(int a, int b){
	int res=1;
	a%=MOD;
	while (b){
		if (b&1)res=(res*a)%MOD;
		a=(a*a)%MOD;
		b>>=1;
	}
	return res;
}

int inv(int num){
	return expo(num, MOD-2);
}

void initfact(){
	fact[0]=1;
	for (int i=1; i<FACTMAX; ++i)fact[i]=(fact[i-1]*i)%MOD;
	invfact[FACTMAX-1]=inv(fact[FACTMAX-1]);
	for (int i=FACTMAX-2; i>=0; --i)invfact[i]=(invfact[i+1]*(i+1))%MOD;
}
 
int ncr(int n, int r){
	if (n<r||r<0)return 0;
	return (((fact[n]*invfact[r])%MOD)*invfact[n-r])%MOD;
}

int gcd(int a, int b){
	while (b){
		int t=a%b;
		a=b;
		b=t;
	}
	return a;
}

int lcm(int a, int b){
	int temp=gcd(a, b);
	a/=temp;
	b/=temp;
	return a*b*temp;
}

void initcatalan(int k){
	cat[0]=1;
	for (int i=1; i<CATALANMAX; ++i)cat[i]=(((fact[2*i]*invfact[i])%MOD)*invfact[i+1])%MOD;
}

struct node;
node* new_node(int s, int e);
node* build(int s, int e);

vector<int> vals;
node *cntst, *sumst;

struct node{
	int s, e, m, val, lazyset, lazyadd;
	node *l, *r;
	void create(){
		if (l==nullptr){
			l = new_node(s, m);
			r = new_node(m+1, e);
		}
	}
	void propagate(){
		if (lazyset!=-1)val=lazyset*(e-s+1);
		val+=lazyadd*(e-s+1);
		if (s!=e && (lazyset!=-1 || lazyadd)){
			if (l==nullptr)create();
			if (lazyset!=-1){
				l->lazyset=lazyset;
				r->lazyset=lazyset;
				l->lazyadd=r->lazyadd=0;
			}
			if (lazyadd){
				l->lazyadd+=lazyadd;
				r->lazyadd+=lazyadd;
			}
		}
		lazyset=-1;
		lazyadd=0;
	}
	node(){}
	node(int S, int E){
		s = S, e = E, m = (s+e)/2;
		val=lazyadd=0;
		lazyset=-1;
		l=r=nullptr;
	}
	void upset(int left, int right, int v){
		propagate();
		if (s==left && e==right)lazyadd=0, lazyset=v;
		else{
			if (l==nullptr)create();
			if (right<=m)l->upset(left, right, v);
			else if (left>m)r->upset(left, right, v);
			else l->upset(left, m, v), r->upset(m+1, right, v);
			r->propagate(), l->propagate();
			val=l->val+r->val;
		}
	}
	void upadd(int left, int right, int v){
		propagate();
		if (s==left && e==right)lazyadd+=v;
		else{
			if (l==nullptr)create();
			if (right<=m)l->upadd(left, right, v);
			else if (left>m)r->upadd(left, right, v);
			else l->upadd(left, m, v), r->upadd(m+1, right, v);
			r->propagate(), l->propagate();
			val=l->val+r->val;
		}
	}
	int query(int left, int right){
		propagate();
		if (s==left && e==right)return val;
		if (right<=m)return l->query(left, right);
		else if (left>m)return r->query(left, right);
		else return l->query(left, m)+r->query(m+1, right);
	}
};

const int poolmax = 1601005 * 2;
node pool[poolmax];
int poolptr;

node* new_node(int s, int e){
	pool[poolptr]=node(s, e);
	return &pool[poolptr++];
}

node* build(int s, int e){
	node* st = new_node(s, e);
	if (s!=e){
		st->l=build(s, st->m);
		st->r=build(st->m+1, e);
	}
	return st;
}

int qry(node* st, int left, int right){
	if (left>right)return 0;
	return st->query(left, right);
}

int get_pos(int v){
	return lower_bound(vals.begin(), vals.end(), v)-vals.begin()+1;
}

int get_val(int pos){
	return vals[pos-1];
}

int kth(node* st, int k){
	st->propagate();
	if (st->s==st->e)return st->s;
	st->l->propagate();
	if (st->l->val>=k)return kth(st->l, k);
	st->r->propagate();
	return kth(st->r, k-st->l->val);
}

void add_pos(int pos, int delta){
	if (!delta)return;
	cntst->upadd(pos, pos, delta);
	sumst->upadd(pos, pos, delta*get_val(pos));
}

void clear_range(int left, int right){
	if (left>right)return;
	cntst->upset(left, right, 0);
	sumst->upset(left, right, 0);
}

void remove_smallest(int k){
	if (k<=0)return;
	cntst->propagate();
	if (k>=cntst->val){
		clear_range(1, (int)vals.size());
		return;
	}
	int p = kth(cntst, k);
	int pref = qry(cntst, 1, p-1);
	clear_range(1, p-1);
	int rem = k-pref;
	if (rem)add_pos(p, -rem);
}

int remove_largest(int left, int right, int k){
	if (left>right || k<=0)return 0;
	int total = qry(cntst, left, right);
	if (!total)return 0;
	if (k>=total){
		int ret = qry(sumst, left, right);
		clear_range(left, right);
		return ret;
	}
	int keep = total-k;
	int before = qry(cntst, 1, left-1);
	int p = kth(cntst, before+keep);
	int pref = qry(cntst, left, p-1);
	int keep_at_p = keep-pref;
	int cntp = qry(cntst, p, p);
	int rem = cntp-keep_at_p;
	int ret = 0;
	if (p+1<=right){
		ret += qry(sumst, p+1, right);
		clear_range(p+1, right);
	}
	if (rem){
		ret += rem*get_val(p);
		add_pos(p, -rem);
	}
	return ret;
}

int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t=1;
	cin>>t;
	while (t--){
		int n, k;
		cin>>n>>k;
		vector<int> a(n+1), b(n+1), c(n+1), d(n+1);
		vector<int> posa(n+1), posc(n+1), lefta(n+1);
		vals.clear();
		vals.reserve(2*n+1);
		vals.pb(0);
		for (int i=1; i<=n; ++i){
			cin>>a[i];
			vals.pb(a[i]);
		}
		for (int i=1; i<=n; ++i)cin>>b[i];
		for (int i=1; i<=n; ++i){
			cin>>c[i];
			vals.pb(c[i]);
		}
		for (int i=1; i<=n; ++i)cin>>d[i];
		sort(vals.begin(), vals.end());
		vals.erase(unique(vals.begin(), vals.end()), vals.end());
		for (int i=1; i<=n; ++i){
			posa[i]=get_pos(a[i]);
			posc[i]=get_pos(c[i]);
			lefta[i]=upper_bound(vals.begin(), vals.end(), a[i])-vals.begin()+1;
		}
		poolptr=0;
		cntst = build(1, (int)vals.size());
		sumst = build(1, (int)vals.size());
		add_pos(get_pos(0), k);
		int ans = 0;
		for (int i=n; i>=1; --i){
			add_pos(posc[i], d[i]);
			if (d[i]>b[i])remove_smallest(d[i]-b[i]);
			int left = lefta[i];
			if (left<=(int)vals.size()){
				int cnt = qry(cntst, left, (int)vals.size());
				int take = min(b[i], cnt);
				if (take){
					ans += remove_largest(left, (int)vals.size(), take)-take*a[i];
					add_pos(posa[i], take);
				}
			}
			remove_smallest(min(b[i], d[i]));
		}
		cout<<ans<<"\n";
	}
}
0