oj.uz

Submission #334733

# Submission time Handle Problem Language Result Execution time Memory
334733 2020-12-09T22:51:29 Z limabeans Trading (IZhO13_trading) C++17
100 / 100
 417 ms 49236 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Correct 16 ms 23788 KB Output is correct
3 Correct 16 ms 23916 KB Output is correct
4 Correct 17 ms 23916 KB Output is correct
5 Correct 18 ms 24044 KB Output is correct
6 Correct 19 ms 24044 KB Output is correct
7 Correct 197 ms 36700 KB Output is correct
8 Correct 228 ms 38616 KB Output is correct
9 Correct 231 ms 39640 KB Output is correct
10 Correct 266 ms 41172 KB Output is correct
11 Correct 257 ms 41052 KB Output is correct
12 Correct 305 ms 43988 KB Output is correct
13 Correct 303 ms 42064 KB Output is correct
14 Correct 305 ms 43060 KB Output is correct
15 Correct 361 ms 45404 KB Output is correct
16 Correct 372 ms 44764 KB Output is correct
17 Correct 343 ms 45148 KB Output is correct
18 Correct 387 ms 49236 KB Output is correct
19 Correct 370 ms 45780 KB Output is correct
20 Correct 417 ms 48980 KB Output is correct