oj.uz

Submission #873875

# Submission time Handle Problem Language Result Execution time Memory
873875 2023-11-16T02:26:20 Z noiaint Trading (IZhO13_trading) C++17
100 / 100
 225 ms 44732 KB 
#include <bits/stdc++.h>

using namespace std;

#define file ""

#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()

#define getbit(x, i) (((x) >> (i)) & 1)
#define bit(x) (1LL << (x))
#define popcount __builtin_popcountll

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
    return l + rd() % (r - l + 1);
}

const int N = 1e6 + 5;
const int mod = (int)1e9 + 7; // 998244353;
const int lg = 25; // lg + 1
const int oo = 1e9;
const long long ooo = 1e18;

template<class X, class Y> bool mini(X &a, Y b) {
    return a > b ? (a = b, true) : false;
}
template<class X, class Y> bool maxi(X &a, Y b) {
    return a < b ? (a = b, true) : false;
}
void add(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    if (a < 0) a += mod;
}

int n, m;
vector<pair<int, int> > a[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    // freopen(file".inp", "r", stdin);
    // freopen(file".out", "w", stdout);

    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
    	int l, r, x;
    	cin >> l >> r >> x;
    	a[l].emplace_back(0, x - l);
    	a[r + 1].emplace_back(1, x - l);
    }

    multiset<int> s;
    for (int i = 1; i <= n; ++i) {
    	for (auto [type, val] : a[i]) {
    		if (type == 0) s.insert(val);
    		else s.erase(s.find(val));
    	}
    	cout << ((int) s.size() ? *s.rbegin() + i : 0) << ' ';
    }

    return 0;
}

/*

*/

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 23896 KB Output is correct
2 Correct 5 ms 23900 KB Output is correct
3 Correct 5 ms 23964 KB Output is correct
4 Correct 5 ms 23896 KB Output is correct
5 Correct 6 ms 23900 KB Output is correct
6 Correct 7 ms 23900 KB Output is correct
7 Correct 96 ms 34264 KB Output is correct
8 Correct 107 ms 35904 KB Output is correct
9 Correct 110 ms 36732 KB Output is correct
10 Correct 135 ms 38456 KB Output is correct
11 Correct 122 ms 37948 KB Output is correct
12 Correct 146 ms 40384 KB Output is correct
13 Correct 154 ms 38708 KB Output is correct
14 Correct 151 ms 39352 KB Output is correct
15 Correct 184 ms 41396 KB Output is correct
16 Correct 182 ms 40780 KB Output is correct
17 Correct 182 ms 41040 KB Output is correct
18 Correct 209 ms 44732 KB Output is correct
19 Correct 197 ms 41660 KB Output is correct
20 Correct 225 ms 44316 KB Output is correct