oj.uz

Submission #915212

# Submission time Handle Problem Language Result Execution time Memory
915212 2024-01-23T13:43:08 Z Whisper Trading (IZhO13_trading) C++14
100 / 100
 150 ms 26424 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using T = tuple<ll, ll, ll, ll>;

#define int long long
#define Base 41
#define sz(a) (int)a.size()
#define FOR(i, a, b) for ( int i = a ; i <= b ; i++ )
#define FORD(i, a, b) for (int i = b; i >= a; i --)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define REPD(i, n) for (int i = n - 1; i >= 0; --i)
#define all(x) x.begin() , x.end()
#define pii pair<int , int>
#define fi first
#define se second
#define Lg(x) 31 - __builtin_clz(x)

#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)

constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int MAX = 3e5 + 5;
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void setupIO(){
    #define name "Whisper"
    //Phu Trong from Nguyen Tat Thanh High School for gifted student
    srand(time(NULL));
    cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr);
    //freopen(name".inp", "r", stdin);
    //freopen(name".out", "w", stdout);
    cout << fixed << setprecision(10);
}

template <class X, class Y>
    bool minimize(X &x, const Y &y){
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize(X &x, const Y &y){
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }


int N, M;
int ans[MAX];
vector<pii> qs[MAX];

void Whisper(){
    cin >> N >> M;
    for (int i = 1; i <= M; ++i){
        int l, r, x; cin >> l >> r >> x;
        qs[l].push_back({r, x - l});
    }

    priority_queue<pii> q;
    for (int i = 1; i <= N; ++i){
        while (q.size() && q.top().se < i) q.pop();
        for (auto&[r, x] : qs[i]) q.push({x, r});
        ans[i] = (q.size() ? q.top().fi + i : 0);
    }
    FOR(i, 1, N) cout << ans[i] << " ";
}


signed main(){
    setupIO();
    int Test = 1;
//    cin >> Test;
    for ( int i = 1 ; i <= Test ; i++ ){
        Whisper();
        if (i < Test) cout << '\n';
    }
}

Compilation message

trading.cpp: In function 'void Whisper()':
trading.cpp:69:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |         for (auto&[r, x] : qs[i]) q.push({x, r});
      |                   ^

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 9048 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 3 ms 8796 KB Output is correct
6 Correct 3 ms 9052 KB Output is correct
7 Correct 70 ms 16964 KB Output is correct
8 Correct 78 ms 18264 KB Output is correct
9 Correct 74 ms 19128 KB Output is correct
10 Correct 94 ms 21476 KB Output is correct
11 Correct 89 ms 19892 KB Output is correct
12 Correct 100 ms 23596 KB Output is correct
13 Correct 113 ms 20732 KB Output is correct
14 Correct 112 ms 21380 KB Output is correct
15 Correct 128 ms 25156 KB Output is correct
16 Correct 113 ms 22596 KB Output is correct
17 Correct 113 ms 23100 KB Output is correct
18 Correct 139 ms 25404 KB Output is correct
19 Correct 150 ms 25860 KB Output is correct
20 Correct 141 ms 26424 KB Output is correct