Submission #508192

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
508192	2022-01-13T07:08:52 Z	ac2hu	Trading (IZhO13_trading)	C++14	100 / 100	389 ms	39996 KB

trading

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
int n,m;
int a[N];
struct tr{
	int l,r,x;
} tr[N];
vector<int> in[N],out[N];
signed main(){
    iostream::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    cin >> n >> m;
    for(int i = 0;i<m;i++){
    	cin >> tr[i].l >> tr[i].r >> tr[i].x;
    	tr[i].l--;
    	tr[i].r--;
    	in[tr[i].l].push_back(i);
    	out[tr[i].r].push_back(i);
    }
    multiset<int> se;
    int c = 0;
    for(int i = 0;i<n;i++){
    	for(auto e : in[i]){
    		se.insert(tr[e].x - c);
    	}
    	// for(auto e : se)cout << e << " ";
    	// cout << endl;
    	if(se.size() == 0)
    		a[i] = 0;
    	else 
    		a[i] = *se.rbegin() + c;
    	c++;
    	for(auto e : out[i]){
    		int val = tr[e].x - tr[e].l;
    		// cerr << e <<  " " << val << endl;
    		se.erase(se.find(val));
    	}
    }
    for(int i = 0;i<n;i++)
    	cout << a[i] << " ";
    cout << "\n";
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	14412 KB	Output is correct
2	Correct	7 ms	14412 KB	Output is correct
3	Correct	8 ms	14412 KB	Output is correct
4	Correct	7 ms	14412 KB	Output is correct
5	Correct	8 ms	14436 KB	Output is correct
6	Correct	9 ms	14548 KB	Output is correct
7	Correct	174 ms	28116 KB	Output is correct
8	Correct	156 ms	29256 KB	Output is correct
9	Correct	168 ms	29656 KB	Output is correct
10	Correct	184 ms	30780 KB	Output is correct
11	Correct	193 ms	31600 KB	Output is correct
12	Correct	233 ms	33660 KB	Output is correct
13	Correct	230 ms	32988 KB	Output is correct
14	Correct	227 ms	34164 KB	Output is correct
15	Correct	266 ms	35356 KB	Output is correct
16	Correct	311 ms	35776 KB	Output is correct
17	Correct	284 ms	36140 KB	Output is correct
18	Correct	367 ms	39208 KB	Output is correct
19	Correct	338 ms	36548 KB	Output is correct
20	Correct	389 ms	39996 KB	Output is correct