oj.uz

Submission #860218

# Submission time Handle Problem Language Result Execution time Memory
860218 2023-10-12T08:09:13 Z AtabayRajabli Trading (IZhO13_trading) C++17
100 / 100
 196 ms 30592 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

// author : AtabeyR

#define pb          push_back
#define pii         pair<int, int>
#define pll         pair<ll, ll>
#define all(v)      v.begin(), v.end()
#define OPT         ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define sec         second
#define fi          first
#define int         ll
#define print(k)    cerr << "Ans : "; cout << k << endl;
#define ins         insert
#define bpc         __builtin_popcountll
#define skip        continue
#define endll        '\n'
#define gcd(a, b)   __gcd(a, b)

typedef long long ll;
typedef unsigned long long ull;
const int oo = 0x3F3F3F3F;
const int ooo = 0x3F3F3F3F3F3F3F3FLL;
const int mod = 998244353;
const int sz = 3e5+6;
using namespace std;
using namespace __gnu_pbds;
template<class T> using ordered_set = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>;

int lcm(int a, int b)
{
    return a*b / (__gcd(a, b));
}
int n, m, k, a[sz], b[sz];

struct dt
{
    int l, r, x;
};

bool cmp(dt a, dt b)
{
    return a.x - a.l > b.x - b.l;
}

void solve(int t)
{  
    cin >> n >> m;

    dt g[m+1];
    for(int i = 1; i<=m; i++)
    {
        cin >> g[i].l >> g[i].r >> g[i].x;
    }

    sort(g+1, g+1+m, cmp);

    set<int> s;
    vector<int> temp;
    for(int i = 1; i<=n; i++)s.ins(i);

    int ans[n+1] = {0};
    for(int i = 1; i<=m; i++)
    {
        auto it = s.lower_bound(g[i].l);
        if(it == s.end())skip;

        for(; it != s.end() && *it <= g[i].r; it++)
        {
            ans[*it] = g[i].x + *it - g[i].l;
            temp.pb(*it);
        }

        for(int i : temp)s.erase(i);
        temp.clear();
    }

    for(int i = 1; i<=n; i++)cout << ans[i] << " " ;
    cout << endll;
}

int32_t main()  
{

    // freopen("i.txt", "r", stdin);
    // freopen("o.txt", "w", stdout);

    OPT
    int t = 1;
    //cin >> t;

    for(int i = 1; i<=t; i++)
        solve(i);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 89 ms 12800 KB Output is correct
8 Correct 104 ms 17240 KB Output is correct
9 Correct 104 ms 17744 KB Output is correct
10 Correct 113 ms 19028 KB Output is correct
11 Correct 122 ms 20508 KB Output is correct
12 Correct 126 ms 21844 KB Output is correct
13 Correct 137 ms 22868 KB Output is correct
14 Correct 136 ms 23360 KB Output is correct
15 Correct 156 ms 25172 KB Output is correct
16 Correct 165 ms 25900 KB Output is correct
17 Correct 155 ms 26192 KB Output is correct
18 Correct 179 ms 27220 KB Output is correct
19 Correct 162 ms 27668 KB Output is correct
20 Correct 196 ms 30592 KB Output is correct