Submission #1037710

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037710		vjudge1	Trading (IZhO13_trading)	C++17	0 / 100	39 ms	65536 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;
template<typename T>
struct Node{
    T val, lazy;
    Node(){
        val = -inf;
        lazy = 0;
    }
};

template<typename T, T (*op)(T, T)>
struct Segment_tree{
    vector<Node<int>> g;
    int n;
    Segment_tree(int n){
        g.resize(4 * n + 5);  
        this->n = n;
    };


    void down(int id){
        T 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, T 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 = op(g[id << 1].val, g[id << 1 | 1].val);
    }


    T 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 op(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,n,l,r, val);
    }

    T get(int l, int r){
        return get(1,1,n,l,r);
    }
};
template<class T> T _max(T a, T b) { return a < b ? b : a; }
void run_case(){
    int n, m;
        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());
    Segment_tree<int , _max> st(n);
    for (auto [p, val] : q){
        // cout << p << " " << val << el;
        if(val < 0){
            st.update(-val,-val,-inf);
        } else{
            if(val == inf){
                cout << max(st.get(1, n), 0ll) << " " ;
                st.update(1,val,1);
            } else{
                st.update(val,val,x[val] - st.get(val,val));
            }
        }
        
    }
    // cout << st.get(1, n) << el;
}

signed main(){
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    run_case();

    runtime();
    return 0;
}

Compilation message (stderr)

trading.cpp: In function 'int main()':
trading.cpp:137:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |         freopen("input.txt","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
trading.cpp:138:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |         freopen("output.txt","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100