Submission #971510

#	Time	Username	Problem	Language	Result	Execution time	Memory
971510		Sunbae	Trading (IZhO13_trading)	C++17	100 / 100	126 ms	16128 KiB

trading

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 3e5 + 5;
tuple<int,int,int> v[N];
ll mx[N], bit[N];
const ll inf = 1e15;
void upd(int i, ll val){
	for(; i<N; i+=i&-i) bit[i] = max(bit[i], val);
}
ll qry(int i){
	ll res = -inf; for(; i; i-=i&-i) res = max(res, bit[i]); return res;
}
signed main(){
	int n, m; scanf("%d %d", &n, &m);
	for(int i = 0, l, r, x; i<m; ++i){
		scanf("%d %d %d", &l, &r, &x);	
		v[i] = make_tuple(r, l, x);
	}
	sort(v, v+m);
	fill(bit, bit+N, -inf);
	for(int i = n, j = m-1; i>=1; --i){
		while(j>=0 && get<0>(v[j]) >= i){
			upd(get<1>(v[j]), get<2>(v[j]) - get<1>(v[j]));
			--j;
		}	
		mx[i] = max(mx[i], i + qry(i));
	}
	for(int i = 1; i<=n; ++i) printf("%lld ", mx[i]);
}

Compilation message (stderr)

trading.cpp: In function 'int main()':
trading.cpp:15:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |  int n, m; scanf("%d %d", &n, &m);
      |            ~~~~~^~~~~~~~~~~~~~~~~
trading.cpp:17:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |   scanf("%d %d %d", &l, &r, &x);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100