Submission #334733

#	Time	Username	Problem	Language	Result	Execution time	Memory
334733		limabeans	Trading (IZhO13_trading)	C++17	100 / 100	417 ms	49236 KiB

trading

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 1e6 + 5;


struct line {
    int l,r,y;
    void read() {
	cin>>l>>r>>y;
    }
};

int n,m;
int ans[maxn];

line a[maxn];
vector<pair<int,int>> ev[maxn];


set<pair<int,int>> st; // (y-x,i)

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);
    
    cin>>n>>m;

    for (int i=1; i<=m; i++) {
	a[i].read();
	ev[a[i].l].push_back({i,+1});
	ev[a[i].r+1].push_back({i,-1});
    }


    for (int i=1; i<=n; i++) {
	for (auto p: ev[i]) {
	    int i=p.first;
	    if (p.second==1) {
		st.insert({a[i].l-a[i].y,i});
	    } else {
		st.erase({a[i].l-a[i].y,i});
	    }
	}

	if (st.empty()) {
	    ans[i]=0;
	    continue;
	}
	int diff=st.begin()->first;
	ans[i] = i-diff;
    }

    for (int i=1; i<=n; i++) {
	cout<<ans[i]<<" ";
    }
    cout<<endl;
    
    
    return 0;
}

• Subtask 1: 100 / 100