Submission #396765

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
396765	2021-04-30T17:41:51 Z	SavicS	Trading (IZhO13_trading)	C++14	100 / 100	397 ms	36596 KB

trading

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ff(i,a,b) for(int i=a;i<=b;i++)
#define fb(i,b,a) for(int i=b;i>=a;i--)

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 300005;
const int inf = 1e9 + 5;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k)  print the k-th smallest number in os(0-based)

int n, m;

vector<int> in[maxn];
vector<int> out[maxn];

int res[maxn];

int main() 
{
    ios::sync_with_stdio(false);
    cout.tie(nullptr);
    cin.tie(nullptr);
    cin >> n >> m;
    ff(i,1,m) {
        int L, R, X;
        cin >> L >> R >> X;

        in[L].pb(X - L);
        out[R + 1].pb(X - L);

    }

    multiset<int> ms;
    ff(i,1,n) {
        for(auto c : in[i])ms.insert(c);
        for(auto c : out[i])ms.erase(ms.find(c));

        res[i] = (sz(ms) == 0 ? 0 : i + *ms.rbegin());

    }

    ff(i,1,n)cout << res[i] << " ";
    cout << endl;

    return 0;
}
/**



// probati bojenje sahovski ili slicno

**/

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	14284 KB	Output is correct
2	Correct	10 ms	14412 KB	Output is correct
3	Correct	10 ms	14416 KB	Output is correct
4	Correct	9 ms	14428 KB	Output is correct
5	Correct	9 ms	14464 KB	Output is correct
6	Correct	13 ms	14516 KB	Output is correct
7	Correct	160 ms	26500 KB	Output is correct
8	Correct	179 ms	27268 KB	Output is correct
9	Correct	223 ms	27700 KB	Output is correct
10	Correct	216 ms	28528 KB	Output is correct
11	Correct	199 ms	29224 KB	Output is correct
12	Correct	261 ms	31128 KB	Output is correct
13	Correct	274 ms	30472 KB	Output is correct
14	Correct	292 ms	31512 KB	Output is correct
15	Correct	325 ms	32552 KB	Output is correct
16	Correct	346 ms	32716 KB	Output is correct
17	Correct	332 ms	33252 KB	Output is correct
18	Correct	364 ms	36072 KB	Output is correct
19	Correct	314 ms	33424 KB	Output is correct
20	Correct	397 ms	36596 KB	Output is correct