oj.uz

Submission #684529

# Submission time Handle Problem Language Result Execution time Memory
684529 2023-01-21T13:27:37 Z NintsiChkhaidze Trading (IZhO13_trading) C++14
100 / 100
 290 ms 24344 KB 
#include <bits/stdc++.h>
#define ll long long
#define left (h<<1),l,((l+r)>>1)
#define right ((h<<1)|1),((l+r)>>1) + 1,r
#define pb push_back
#define s second
#define f first
#define pii pair<int,int>
#define int ll
using namespace std;
 
const int N = 300005,inf = -1e18;
int t[4*N],lz[4*N];
 
void push(int h){
    if (lz[h] == inf) return;
    lz[h*2]=max(lz[h*2],lz[h]);
    lz[h*2+1]=max(lz[h*2+1],lz[h]);
 
    t[h*2]=max(t[h*2],lz[h]);
    t[h*2+1]=max(t[h*2+1],lz[h]);

    lz[h] = inf;
}
void upd(int h,int l,int r,int L,int R,int x){
    if (r < L || R < l) return;
    if (L <= l && r <= R){
        t[h] = max(t[h],x);
        lz[h] = max(lz[h],x);
        return;
    }
    push(h);
    upd(left,L,R,x);
    upd(right,L,R,x);
    t[h] = max(t[h*2],t[h*2+1]);
}
 
int get(int h,int l,int r,int idx){
    if (l == r) return t[h];
    push(h);
    if (idx > (l + r)>>1) return get(right,idx);
    return get(left,idx);
}
void build(int h,int l,int r){
    t[h] = lz[h] = inf;
    if (l==r) return;
    build(left);build(right);
}
signed main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    
    int n,q;
    cin>>n>>q;
 
    build(1,1,n);
    while (q--){
        int l,r,x;
        cin>>l>>r>>x;
        upd(1,1,n,l,r,x-l);
    }
 
    for (int i = 1; i <= n; i++){
        int p = get(1,1,n,i);
        if (p == inf) cout<<0<<" "; 
        else cout<<p + i<<" ";
    }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 130 ms 12224 KB Output is correct
8 Correct 145 ms 12752 KB Output is correct
9 Correct 159 ms 12876 KB Output is correct
10 Correct 163 ms 12872 KB Output is correct
11 Correct 189 ms 13660 KB Output is correct
12 Correct 204 ms 13688 KB Output is correct
13 Correct 186 ms 14152 KB Output is correct
14 Correct 194 ms 13892 KB Output is correct
15 Correct 206 ms 14656 KB Output is correct
16 Correct 240 ms 14668 KB Output is correct
17 Correct 228 ms 22992 KB Output is correct
18 Correct 236 ms 23504 KB Output is correct
19 Correct 290 ms 23108 KB Output is correct
20 Correct 264 ms 24344 KB Output is correct