Submission #16917

#	Time	Username	Problem	Language	Result	Execution time	Memory
16917		erdemkiraz	Trading (IZhO13_trading)	C++98	100 / 100	401 ms	26480 KiB

trading

#include <bits/stdc++.h>

using namespace std;

#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++)

typedef long long ll;
typedef pair < int, int > ii;

const int inf = 1e9 + 333;
const ll linf = 1e18 + inf;

const int N = 3e5 + 5;

int n, m;
int l[N], r[N], a[N], ans[N];
vector < int > event[N];

int main() {

    scanf("%d %d", &n, &m);

    for(int i = 1; i <= m; i++) {
        scanf("%d %d %d", l + i, r + i, a + i);
        event[l[i]].push_back(i);
        event[r[i] + 1].push_back(-i);
    }

    multiset < int > s;

    for(int i = 1; i <= n; i++) {
        foreach(it, event[i]) {
            int x = *it;
            if(x > 0) {
                s.insert(l[x] - a[x]);
            }
            else {
                x = -x;
                s.erase(s.find(l[x] - a[x]));
            }
        }
        if(s.empty())
            continue;
        ans[i] = -*s.begin() + i;
    }

    for(int i = 1; i <= n; i++)
        printf("%d ", ans[i]);

    puts("");

    return 0;

}

• Subtask 1: 100 / 100