# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
41323 | wzy | Trading (IZhO13_trading) | C++11 | 1378 ms | 65536 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define F first
#define pb push_back
#define S second
int n , m , carry[1000005];
vector<pii> st [1000005], ed[1000005];
multiset<pii> ans;
int main(){
scanf("%d%d" , &n , &m);
for(int i = 0 ; i < m ; i++){
int l ,r , v;
scanf("%d%d%d" , &l , &r , &v);
st[l].pb(pii(r, v));
}
for(int i = 0 ; i <= n ; i++) carry[i] = 0;
for(int i = 1 ; i <= n ; i++){
while(!st[i].empty()){
ans.insert(pii(i -st[i].back().S , st[i].back().F));
ed[st[i].back().F].pb(pii(pii( i - st[i].back().S , st[i].back().F)));
st[i].pop_back();
}
if(!ans.empty()){
pii u = *ans.begin();
carry[i] = max(carry[i] , i - u.F);
}
while(ed[i].size()){
ans.erase(ans.find(ed[i].back()));
ed[i].pop_back();
}
}
for(int i = 1 ; i <= n; i++) printf("%d " , carry[i]);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |