oj.uz

Submission #875900

# Submission time Handle Problem Language Result Execution time Memory
875900 2023-11-20T17:44:25 Z Arpi2007 Trading (IZhO13_trading) C++14
100 / 100
 151 ms 27848 KB 
#include <iostream>
#include <queue>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <utility>
#include <stack>
#include <math.h>
#include <climits>
#include <stdlib.h>
#include <stdio.h>
#include <iomanip>
#include <assert.h>
using namespace std;
 
#define ll long long
#define ld long double
#define ull unsigned long long
#define ub upper_bound
#define lb lower_bound 
#define ff first
#define ss second
#define mpr make_pair
#define vi vector<int>
#define vll vector<ll>
#define pii pair<int,int>
#define vpi vector<pii>
#define pb push_back
#define pob pop_back
#define mii map<int,int>
#define vpl vector<pair<ll, ll>>
#define pll pair<ll,ll>
#define all(v) v.begin(),v.end()
#define sz(x) x.size()
#define clr(x) x.clear()
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define print(x) cout<<"x="<<x<<endl;
 
ll MOD = 1e9 + 7;
ll MOD2 = 998244353;
 
void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
 
void setprecision(int x) {
 
    cout.setf(ios::fixed | ios::showpoint);
    cout.precision(x);
}
 
/*void setIO(string name = "") {
    if ((int)name.size() > 0) {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
}*/
 
ll gcd(ll a, ll b)
{
    if(b == 0) {
            return a;
    }
    else {
        return gcd(b, a % b);
    }
}
 
int qannum(int n) {
    ll ans = 0;
    while (n != 0) {
        ans++;
        n /= 10;
    }
    return ans;
}
 
ll lcm(ll a, ll b) {
    return (a * b) / gcd(a, b);
}
 
 
ll factorial(ll n) {
    ll ans = 1;
    for (int i = 1; i <= n; i++) {
        ans *= i;
        ans %= MOD2;
    }
    return ans;
}
 
bool isPrime(int n)
{
    if (n <= 1) {
        return false;
    }
    if (n == 2) {
        return true;
    }
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0)
            return false;
    }
    return true;
}
 
int sumnum(int n) {
    int ans = 0;
    while (n != 0) {
        ans += n % 10;
        n /= 10;
    }
    return ans;
}
 
ll bpow_mod(ll a, ll b, ll mod)
{
	ll ans = 1;
	while (b) {
		if ((b & 1) == 1) {
			ans *= a;
			ans %= mod;
		}
		b >>= 1;
		a *= a;
		a %= mod;
	}
	return ans;
}
 
bool sortbysec(const pair<int, int>& a,
    const pair<int, int>& b)
{
    return (a.second < b.second);
}

ll factoriall(ll n, int j) {
    ll ans = 1;
    for (int i = j; i <= n; i++) {
        ans *= i;
        ans %= MOD2;
    }
    return ans;
}
 
void precalc(){
    return;
}
 
const int N = 1e6+ 10;
ll t[4 * N];
ll curl[4 * N], ind[N];
void bld(int l, int r, int v){
    curl[v] = l;
    if(l == r){
        ind[l] = v;
    }
    else{
        int m = ( r + l ) / 2;
        bld(l, m, 2 * v);
        bld(m + 1, r, 2 * v + 1);
    }
}

void upd(int l, int r, int tl, int tr, int v, ll val){
    if(l == tl && tr == r){
        t[v] = max(t[v], val);
    }
    else{
        int m = (tl + tr) / 2;
        if(m >= r){
            upd(l, r, tl, m, 2 * v, val);
        }
        else if(l > m){
            upd(l, r, m + 1, tr, 2 * v + 1, val);
        }
        else{
            upd(l, m, tl, m, 2 * v, val);
            upd(m + 1, r, m + 1, tr, 2 * v + 1, val + (ll)(m - l + 1));
        }
    }
}

ll qry(int pos){
    int i = pos;
    pos = ind[pos];
    ll ans = 0;
    while(pos){
        if(t[pos] > 0){
            ans = max(ans, t[pos] + (ll)(i - curl[pos]));
        }
        pos /= 2;
    }
    return ans;
}



void solve() {
    int n, m;
    cin >> n >> m;
    bld(1, n, 1);
    for(int i = 0; i < m; ++i){
        int l, r;ll x;
        cin >> l >> r >> x;
        upd(l, r, 1, n, 1, x);
    }
     for(int i = 1; i <= n; ++i){
        cout << qry(i) << ' ';
    } 
    cout << "\n";
}

 
 
void cases() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}
 
int main() {
    //setIo
    fastio();
    precalc();
    //cases();
    solve();
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 2 ms 2648 KB Output is correct
7 Correct 80 ms 15128 KB Output is correct
8 Correct 87 ms 16468 KB Output is correct
9 Correct 82 ms 15764 KB Output is correct
10 Correct 84 ms 14584 KB Output is correct
11 Correct 112 ms 17364 KB Output is correct
12 Correct 98 ms 16096 KB Output is correct
13 Correct 109 ms 17228 KB Output is correct
14 Correct 110 ms 16160 KB Output is correct
15 Correct 119 ms 17492 KB Output is correct
16 Correct 119 ms 17236 KB Output is correct
17 Correct 115 ms 23444 KB Output is correct
18 Correct 135 ms 25672 KB Output is correct
19 Correct 149 ms 23632 KB Output is correct
20 Correct 151 ms 27848 KB Output is correct