Submission #45631542

---

Source Code Expand

// Problem: E - Somen Nagashi
// Contest: AtCoder - Toyota Programming Contest 2023#5（AtCoder Beginner Contest 320）
// URL: https://atcoder.jp/contests/abc320/tasks/abc320_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(x) (x).begin(), (x).end()
const double PI = 4*atan(1);
template<typename T>
void chmax(T& a, T const b) { a = max(a, b); }
template<typename T>
void chmin(T& a, T const b) { a = min(a, b); }
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9+7;
const int MAX_N = 2e6+10;

int n, m;
ll t[MAX_N], w[MAX_N];
ll s[MAX_N], ans[MAX_N];

int N;
ll seg_tree[4*MAX_N];


void init()
{
	N=1;
	while(N < n) N *= 2;
}

ll query(int a, int b, int k, int l, int r)
{
	if(r<=a||b<=l) return LINF;
	else if(a<=l&&r<=b) return seg_tree[k];
	else{
		int mid=(l+r)/2;
		auto le = query(a, b, 2*k+1, l,  mid);
		auto ri = query(a, b, 2*k+2, mid, r);
		return min(le,ri);
	}
}

ll query(int r)
{
	return query(0,r+1,0,0,N);
}
 
int get(ll target)
{
	// first idx such that time <= t
	if(query(n-1) > target) return n;
	int lo=-1, hi=n-1;
	while(lo + 1 < hi){
		int mid = (lo+hi)/2;
		if(query(mid) <= target) hi = mid;
		else lo = mid;
	}
	return hi;
}
 
void update(int idx, ll val)
{
	idx += N - 1;
	seg_tree[idx] = val;
	while(idx > 0) {
		idx = (idx - 1)/2;
		seg_tree[idx] = min(seg_tree[idx*2+1],seg_tree[idx*2+2]);
	}
}

void solve()
{
	init();
	for(int i=0;i<m;++i){
		int idx = get(t[i]);
		if(idx >= n) continue;
		ans[idx] += w[i];
		update(idx, s[i]+t[i]);
	}
	for(int i=0;i<n;++i) cout<<ans[i]<<'\n';
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	cin >> n >> m;
	for(int i=0;i<m;++i) cin >> t[i] >> w[i] >> s[i];
	solve();
	return 0;
}

Submission Info

Judge Result