Submission #90886

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
90886	2018-12-25T05:54:15 Z	inom	Trading (IZhO13_trading)	C++14	100 / 100	496 ms	45096 KB

trading

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int N = 300300;
const int MAXN = 4 * N;
const int INF = 1e15 + 7;
 
struct trader {
    int l, r, x, b;
};

int TN = 1;

int n, m;
int t[MAXN];
int d[MAXN];
trader a[N];

bool cmp(trader x, trader y) {
    if (x.b < y.b) {
        return true;
    }
    if (x.b > y.b) {
        return false;
    }
    else {
        if (x.l < y.l) {
            return true;
        }
        if (x.l > y.l) {
            return false;
        }
        else {
            if (x.r < y.r) {
                return true;
            }
            if (x.r > y.r) {
                return false;
            }
            return false;
        }
    }
    return false;
}

void push(int v) {
    if (d[v] != -INF) {
        t[v << 1] = t[v << 1 | 1] = d[v];
        d[v << 1] = d[v << 1 | 1] = d[v];
        d[v] = -INF; return;
    }
}

void update(int v, int tl, int tr, int l, int r, int val) {
    if (tl > r || tr < l || l > r) {
        return;
    }
    if (tl == l && tr == r) {
        if (t[v] < val) {
            t[v] = val; d[v] = val;
            return;
        }
        return;
    }
    // cout << v << " " << tl << " " << tr << " " << l << " " << r << " " << val << "\n";
    push(v);
    int tm = (tl + tr) >> 1;
    update(v << 1, tl, tm, l, min(tm, r), val);
    update(v << 1 | 1, tm + 1, tr, max(tm + 1, l), r, val);
}

int get(int v, int tl, int tr, int pos) {
    if (tl == tr) {
        if (d[v] != -INF) {
            t[v] = d[v];
        }
        return t[v];
    }
    push(v);
    int tm = (tl + tr) >> 1;
    if (pos <= tm) {
        return get(v << 1, tl, tm, pos);
    } else {
        return get(v << 1 | 1, tm + 1, tr, pos);
    }
}

void solve() {
    // scanf("%d %d", &n, &m);
    fill(t, t + MAXN, -INF);
    fill(d, d + MAXN, -INF);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        // scanf("%d %d %d", &a[i].l, a[i].r, a[i].x);
        cin >> a[i].l >> a[i].r >> a[i].x;
        a[i].b = a[i].x - a[i].l;
        // cout << a[i].l << " " << a[i].r << " " << a[i].b << "\n";
        /*
        update(1, 1, n, a[i].l, a[i].r, a[i].b);
        cout << i << " ";
        cout << "come back\n";
        */
    }
    sort(a + 1, a + 1 + m, cmp);
    /*for (int i = 1; i <= m; i++) {
        // cout << a[i].b << " " << a[i].l << " " << a[i].r << " " << a[i].x << "\n";
        // printf("%d %d %d %d\n", a[i].b, a[i].l, a[i].r, a[i].x);
    }*/
    for (int i = 1; i <= m; i++) {
        update(1, 1, n, a[i].l, a[i].r, a[i].b);
    }
    for (int i = 1; i <= n; i++) {
        int ans = get(1, 1, n, i);
        if (ans == -INF) {
            cout << 0 << " ";
        } else {
            cout << ans + i << " ";
        }
    }
    return;
}

signed main() {
    // in; out; // cin >> TN;
    while (TN--) { solve(); }
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	19064 KB	Output is correct
2	Correct	16 ms	19316 KB	Output is correct
3	Correct	16 ms	19368 KB	Output is correct
4	Correct	17 ms	19368 KB	Output is correct
5	Correct	16 ms	19368 KB	Output is correct
6	Correct	17 ms	19424 KB	Output is correct
7	Correct	245 ms	24860 KB	Output is correct
8	Correct	266 ms	25696 KB	Output is correct
9	Correct	281 ms	29120 KB	Output is correct
10	Correct	303 ms	33116 KB	Output is correct
11	Correct	315 ms	37208 KB	Output is correct
12	Correct	344 ms	42056 KB	Output is correct
13	Correct	344 ms	42380 KB	Output is correct
14	Correct	348 ms	42380 KB	Output is correct
15	Correct	396 ms	43276 KB	Output is correct
16	Correct	425 ms	43612 KB	Output is correct
17	Correct	401 ms	43612 KB	Output is correct
18	Correct	430 ms	43944 KB	Output is correct
19	Correct	435 ms	43944 KB	Output is correct
20	Correct	496 ms	45096 KB	Output is correct