제출 #90771

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
90771		inom	거래 (IZhO13_trading)	C++14	0 / 100	11 ms	9976 KiB

trading

#include<bits/stdc++.h>
 
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;
}

void push(int v) {
    if (d[v] != 0) {
        t[v << 1] = t[v << 1 | 1] = d[v];
        d[v << 1] = d[v << 1 | 1] = d[v];
        d[v] = 0; 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;
        }
    }
    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] != 0) {
            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);
    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;
    }
    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);
    }*/
    fill(t, t + MAXN, -INF);
    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;
}

컴파일 시 표준 에러 (stderr) 메시지

trading.cpp:7:22: warning: overflow in implicit constant conversion [-Woverflow]
 const int INF = 1e15 + 7;
                 ~~~~~^~~

• Subtask 1: 0 / 100