oj.uz

Submission #339711

# Submission time Handle Problem Language Result Execution time Memory
339711 2020-12-26T04:10:44 Z talant117408 Trading (IZhO13_trading) C++17
100 / 100
 339 ms 13420 KB 
/*
    Code written by Talant I.D.
*/
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
 
//using namespace __gnu_pbds;
using namespace std;
//typedef tree <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
  
#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) int((v).size())
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define OK cout << "OK" << endl;
  
inline bool isvowel(char ch){
    ch = tolower(ch);
    return (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u');
}
  
inline bool isprime(int n){
    if(n < 2 || (n%2 == 0 && n != 2)) return false;
    for(int i = 3; i*i <= n; i++)
        if(n%i == 0) return false;
    return true;
}
 
class Union{
    private:
        vector <int> saizu, link;
    public:
        Union(int n){
            saizu.assign(n, 1); link.resize(n); 
            iota(all(link), 0);
        }
        int find(int n){
            if(link[n] == n) return n;
            return link[n] = find(link[n]);
        }
        int same(int a, int b){
            return find(a) == find(b);
        }
        void unite(int a, int b){
            if(same(a, b)) return;
             
            a = find(a); b = find(b);
            if(saizu[a] < saizu[b]) swap(a, b);
             
            saizu[a] += saizu[b];
            link[b] = a;
        }
        int getsize(int a){
            return saizu[find(a)];
        }
};
 
const int mod = 1e9+7;
 
ll mode(ll a){
    a %= mod;
    if(a < 0) a += mod;
    return a;
}
 
ll subt(ll a, ll b){
    return mode(mode(a)-mode(b));
}
 
ll add(ll a, ll b){
    return mode(mode(a)+mode(b));
}
 
ll mult(ll a, ll b){
    return mode(mode(a)*mode(b));
}
 
ll binpow(ll a, ll b){
    ll res = 1;
    while(b){
        if(b&1) res = mult(res, a);
        a = mult(a, a);
        b >>= 1;
    }
    return res;
}

const int N = 3e5+7;
int tree[N*4], lz[N*4], curl;

void push(int v, int l, int r){
    if(lz[v] != 0){
        int mid = (l+r) >> 1;
        tree[v] = max(tree[v], lz[v]+(r-l));
        if(l != r){
            lz[v*2] = max(lz[v*2], lz[v]);
            lz[v*2+1] = max(lz[v*2+1], lz[v]+(mid-l+1));
        }
        lz[v] = 0;
    }
}

void update(int v, int l, int r, int ql, int qr, int x){
    int mid = (l+r) >> 1;
    push(v, l, r);
    if(l > qr || ql > r) return;
    if(ql <= l && r <= qr){
        lz[v] = max(lz[v], x+(l-curl));
        return;
    }
    update(v*2, l, mid, ql, qr, x);
    update(v*2+1, mid+1, r, ql, qr, x);
}

void build(int v, int l, int r){
    push(v, l, r);
    if(l == r){
        return;
    }
    int mid = (l+r) >> 1;
    build(v*2, l, mid);
    build(v*2+1, mid+1, r);
}

int get(int v, int l, int r, int pos){
    if(l == r){
        return tree[v];
    }
    int mid = (l+r) >> 1;
    if(pos <= mid) return get(v*2, l, mid, pos);
    else return get(v*2+1, mid+1, r, pos);
}

int main(){
    do_not_disturb
    
    int n, q;
    cin >> n >> q;
    while(q--){
        int l, r, x;
        cin >> l >> r >> x;
        curl = l;
        update(1, 1, n, l, r, x);
    }
    build(1, 1, n);
    for(int i = 1; i <= n; i++){
        cout << get(1, 1, n, i) << ' ';
    }
    
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 3 ms 492 KB Output is correct
7 Correct 157 ms 7040 KB Output is correct
8 Correct 177 ms 8300 KB Output is correct
9 Correct 190 ms 7532 KB Output is correct
10 Correct 196 ms 6400 KB Output is correct
11 Correct 206 ms 8940 KB Output is correct
12 Correct 232 ms 7788 KB Output is correct
13 Correct 237 ms 8940 KB Output is correct
14 Correct 247 ms 7916 KB Output is correct
15 Correct 269 ms 9196 KB Output is correct
16 Correct 288 ms 9068 KB Output is correct
17 Correct 258 ms 11372 KB Output is correct
18 Correct 294 ms 12780 KB Output is correct
19 Correct 283 ms 10988 KB Output is correct
20 Correct 339 ms 13420 KB Output is correct