CSES - HIIT Open 2019 - Results
Submission details
Task:Final Array
Sender:Varokaa J:tä
Submission time:2019-05-25 13:12:39 +0300
Language:C++
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.21 sdetails
#2ACCEPTED0.17 sdetails
#3ACCEPTED0.02 sdetails

Code

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N (1<<19)

ll t[2*N];

void push(int s, int l, int r){
    if(l+1 == r || t[s] == 0) return;
    
    t[2*s] = max(t[2*s], t[s]);
    t[2*s+1] = max(t[2*s+1], t[s] + (ll)(r-l)/2);
    t[s] = 0;
}

void upd(int s, int l, int r, int a, int b, ll x){
    if(a==l && b==r) t[s] = max(t[s], x);
    else{
        push(s, l, r);
        int m = (l+r)/2;
        if(a < m) upd(2*s, l, m, a, min(b, m), x);
        if(b > m) upd(2*s+1, m, r, max(a, m), b, x + (ll)max(0, m-a));
    }
}

void asd(int s, int l, int r){
    if(l + 1 == r) return;
    push(s, l, r);
    int m = (l+r)/2;
    asd(2*s, l, m);
    asd(2*s+1, m, r);
}
int main() {
    int n, m;
    cin >> n >> m;
    while(m--){
        int a, b;
        ll x; cin >> a >> b >> x;
        upd(1, 0, N, a, b+1, x);        
    }
    asd(1, 0, N);
    for(int i=1; i<=n; ++i) cout << t[N+i] << " ";
    cout << "\n";
}

Test details

Test 1

Verdict: ACCEPTED

input
100000 100000
29706 39977 913671103
20575 89990 878449866
1691 70785 229168045
81099 81323 611730238
...

correct output
227121122 450258482 450258483 ...

user output
227121122 450258482 450258483 ...
Truncated

Test 2

Verdict: ACCEPTED

input
100000 100000
1 100000 1
1 100000 2
1 100000 3
1 100000 4
...

correct output
100000 100001 100002 100003 10...

user output
100000 100001 100002 100003 10...
Truncated

Test 3

Verdict: ACCEPTED

input
8 2
1 4 1
1 8 1

correct output
1 2 3 4 5 6 7 8

user output
1 2 3 4 5 6 7 8