제출 #1037745

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1037745		Hnant_nauX	거래 (IZhO13_trading)	C++17	100 / 100	307 ms	43700 KiB

trading

#include <climits>
#include <iostream>
#include <algorithm>
#include <time.h>
#include <ctype.h>
#include <iomanip>
#include <numeric>
#include <functional>
#include <utility>
#include <tgmath.h>
#include <string>
#include <cstring>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <stack>
#define el '\n'
#define br  cout << "-------------------------------" << el;
using ll = long long;
using namespace std;
#define int ll
const ll mod = 1e9 + 7;
#ifndef ONLINE_JUDGE
    clock_t tStart = clock();
#endif
void runtime(){
    #ifndef ONLINE_JUDGE
        fprintf(stderr, ">> Runtime: %.10fs\n", (double) (clock() - tStart) / CLOCKS_PER_SEC);
    #endif
}
// --------------------------------------------------------------------------- //
const int N = 3e5+5;
int inf = 2e18;
struct Node{
    int val, lazy;
    Node(){
        val = -inf;
        lazy = 0;
    }
};
Node g[4 * N];
int n, m;
void down(int id){
    int t = g[id].lazy;
    g[id << 1].lazy += t;
    g[id << 1].val += t;
    g[id << 1 | 1].lazy += t;
    g[id << 1 | 1].val += t;
    g[id].lazy = 0;
}


void update(int id,int l, int r, int u, int v, int val){
    if(l > v || r < u) return;
    if(l >= u && r <= v) {
        g[id].val += val;
        g[id].lazy += val;
        // cout << id << " " << g[id].val << " "<< g[id].lazy << el;
        return;
    }
    int mid = (l + r) >> 1;
    down(id);
    update(id << 1, l, mid, u, v, val);
    update(id << 1 | 1, mid + 1, r, u, v, val);
    g[id].val = max(g[id << 1].val, g[id << 1 | 1].val);
}


int get(int id, int l, int r, int u ,int v){
    if(l > v || r < u) return -inf;
    if(l >= u && r <= v){
        return g[id].val;
    }

    int mid = (l + r) >> 1;
    down(id);
    return max(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
}

void update(int l, int r, int val){
    update(1,1,m,l,r, val);
}

int get(int l, int r){
    return get(1,1,m,l,r);
}
void run_case(){
        cin >> n >> m;

    vector<pair<int, int>> q;
    for (int i = 1; i <= n; i++){
        q.push_back({i, inf});
    }
    int x[m + 1];
    for (int i = 1; i <= m; i++){
        int l, r;
            cin >> l >> r >> x[i];
        q.push_back({l, i});
        q.push_back({r + 1, -i});
    }
    
    sort(q.begin(), q.end());
    for (auto [p, val] : q){
        // cout << p << " " << val << el;
        if(val < 0){
            update(-val,-val,-inf);
        } else{
            if(val == inf){
                cout << max(get(1, m), 0ll) << " ";
                update(1,val,1);
            } else{
                update(val,val,x[val] - get(val,val));
            }
        }
        
    }
    // cout << st.get(1, n) << el;
}

signed main(){
    
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    run_case();

    runtime();
    return 0;
}

• Subtask 1: 100 / 100