oj.uz

Submission #16917

# Submission time Handle Problem Language Result Execution time Memory
16917 2015-10-25T12:43:55 Z erdemkiraz Trading (IZhO13_trading) C++
100 / 100
 401 ms 26480 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 13444 KB Output is correct
2 Correct 0 ms 13444 KB Output is correct
3 Correct 0 ms 13444 KB Output is correct
4 Correct 4 ms 13444 KB Output is correct
5 Correct 0 ms 13444 KB Output is correct
6 Correct 6 ms 13444 KB Output is correct
7 Correct 177 ms 19520 KB Output is correct
8 Correct 185 ms 20696 KB Output is correct
9 Correct 212 ms 21000 KB Output is correct
10 Correct 256 ms 21600 KB Output is correct
11 Correct 205 ms 21660 KB Output is correct
12 Correct 286 ms 23604 KB Output is correct
13 Correct 277 ms 21804 KB Output is correct
14 Correct 288 ms 22480 KB Output is correct
15 Correct 313 ms 23332 KB Output is correct
16 Correct 380 ms 21908 KB Output is correct
17 Correct 331 ms 23240 KB Output is correct
18 Correct 376 ms 26480 KB Output is correct
19 Correct 363 ms 23064 KB Output is correct
20 Correct 401 ms 24684 KB Output is correct