제출 #1029663

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1029663		vjudge1	거래 (IZhO13_trading)	C++17	100 / 100	815 ms	41540 KiB

trading

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define all(v) begin(v), end(v)
#define pi pair<int, int>
#define vi vector<int>
using namespace std;
const int maxn = 3e5+3;
int n, k, l[maxn], r[maxn], x[maxn], ans[maxn];
vector<int> add[maxn], del[maxn];
multiset<int> mt;
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k;
    for(int i = 1; i <= k; i++){
        cin >> l[i] >> r[i] >> x[i];
        x[i] -= l[i];
    }
    for(int i = 1; i <= k; i++){
        add[l[i]].push_back(i);
        del[r[i]+1].push_back(i);
    }
    for(int i = 1; i <= n; i++){
        cerr << i << "\n";
        for(auto y:add[i]) mt.insert(x[y]);
        for(auto y:del[i]) mt.erase(mt.find(x[y]));
        if(mt.size()) ans[i] = i + *mt.rbegin();
    }
    for(int i = 1; i <= n; i++) cout << ans[i] << " ";
    return 0;
}

• Subtask 1: 100 / 100