oj.uz

Submission #47548

# Submission time Handle Problem Language Result Execution time Memory
47548 2018-05-05T03:21:15 Z tieunhi Trading (IZhO13_trading) C++14
100 / 100
 315 ms 26476 KB 
#include <bits/stdc++.h>
#define pii pair<int, int>
#define mp make_pair
#define F first
#define S second
#define PB push_back
#define mid (r + l)/2
#define N 300005
#define maxc 1000000007

using namespace std;

int n, m;

struct IntervalTree
{
    int t[N << 2];
    void build()
    {
        for (int i = 0; i < (N << 2); i++)
            t[i] = -maxc;
    }
    void update(int l, int r, int id, int x, int y, int val)
    {
        if (l > y || r < x) return;
        if (l >= x && r <= y)
        {
            t[id] = max(t[id], val);
            return;
        }
        update(l, mid, id*2, x, y, val);
        update(mid+1, r, id*2+1, x, y, val);
    }
    int get(int l, int r, int id, int x)
    {
        if (l > x || r < x) return -maxc;
        if (l == r)
            return t[id];
        int z = t[id];
        int a = get(l, mid, id*2, x);
        int b = get(mid+1, r, id*2+1, x);
        return max({z, a, b});
    }
}t;
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("INP.TXT", "r", stdin);
    cin >> n >> m;
    t.build();
    for (int i = 1; i <= m; i++)
    {
        int u, v, w; cin >> u >> v >> w;
        w -= (u-1);
        t.update(1, n, 1, u, v, w);
    }
    for (int i = 1; i <= n; i++)
    {
        int res = t.get(1, n, 1, i);
        if (res == -maxc) cout <<0<<" ";
        else cout <<t.get(1, n, 1, i) + i - 1<<" ";
    }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4984 KB Output is correct
2 Correct 5 ms 5224 KB Output is correct
3 Correct 6 ms 5224 KB Output is correct
4 Correct 6 ms 5224 KB Output is correct
5 Correct 7 ms 5224 KB Output is correct
6 Correct 8 ms 5224 KB Output is correct
7 Correct 144 ms 8820 KB Output is correct
8 Correct 166 ms 12356 KB Output is correct
9 Correct 183 ms 15688 KB Output is correct
10 Correct 174 ms 19060 KB Output is correct
11 Correct 201 ms 23652 KB Output is correct
12 Correct 197 ms 25948 KB Output is correct
13 Correct 219 ms 26176 KB Output is correct
14 Correct 213 ms 26176 KB Output is correct
15 Correct 243 ms 26176 KB Output is correct
16 Correct 256 ms 26176 KB Output is correct
17 Correct 242 ms 26316 KB Output is correct
18 Correct 263 ms 26352 KB Output is correct
19 Correct 253 ms 26352 KB Output is correct
20 Correct 315 ms 26476 KB Output is correct