Submission #502127

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
502127	2022-01-05T10:28:17 Z	Aktan	Trading (IZhO13_trading)	C++17	100 / 100	547 ms	33500 KB

trading

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define int long long
#define ft first
#define sc second
using namespace std;
const int mod=1e9+7,INF=1e17,N=3e5+5;

int a[N],b[N],c[N];
main(){
    int n,m;
    cin >> n >> m;
    multiset<pair<pair<int,int>,int>> v;
    for(int i=0;i<m;i++){
    	cin >> a[i] >> b[i] >> c[i];
    	v.insert({{a[i],b[i]},c[i]-a[i]});
	}
	multiset<pair<int,int>> v1;
	for(int i=1;i<=n;i++){
		while(!v.empty() && v.begin()->ft.ft<=i){
			v1.insert({v.begin()->sc,v.begin()->ft.sc});
			v.erase(v.begin());
		}
		while(!v1.empty() && (--v1.end())->sc < i){
			v1.erase((--v1.end()));
		}
		if(v1.empty()){
			cout << 0 << " ";
		}
		else{
			auto it=v1.end();
			it--;
			cout << it->ft+i << " ";
		}
	}
}

Compilation message

trading.cpp:13:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   13 | main(){
      | ^~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	304 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	304 KB	Output is correct
5	Correct	3 ms	460 KB	Output is correct
6	Correct	4 ms	524 KB	Output is correct
7	Correct	247 ms	17180 KB	Output is correct
8	Correct	274 ms	18720 KB	Output is correct
9	Correct	266 ms	19448 KB	Output is correct
10	Correct	375 ms	21060 KB	Output is correct
11	Correct	308 ms	21624 KB	Output is correct
12	Correct	351 ms	24280 KB	Output is correct
13	Correct	370 ms	24356 KB	Output is correct
14	Correct	409 ms	24880 KB	Output is correct
15	Correct	475 ms	27748 KB	Output is correct
16	Correct	485 ms	28800 KB	Output is correct
17	Correct	430 ms	27852 KB	Output is correct
18	Correct	489 ms	29608 KB	Output is correct
19	Correct	481 ms	29228 KB	Output is correct
20	Correct	547 ms	33500 KB	Output is correct