제출 #1267587

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1267587		quangminh412	Treatment Project (JOI20_treatment)	C++17	100 / 100	146 ms	37948 KiB

treatment

/*
  Ben Watson

  Quang Minh MasterDDDDD
*/

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const string name = "test";

void solve();
signed main()
{
    if (fopen((name + ".inp").c_str(), "r"))
    {
        freopen((name + ".inp").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    solve();

    return 0;
}

// main program
const ll oo = 0x3f3f3f3f3f3f3f;
const int maxm = 1e5 + 1;

int T[maxm], L[maxm], R[maxm], C[maxm];
vector<pair<int, int>> proc;
vector<ll> dist(maxm, oo);
pair<int, int> arr[maxm];
int n, m;

struct Node
{
    vector<pair<int, int>> v;
    int ptr;

    Node() : ptr(0) {};
    Node(pair<int, int> val) { v.push_back(val); ptr = 0; }
    Node operator + (const Node& other)
    {
        Node res;
        res.v.resize(v.size() + other.v.size());
        merge(v.begin(), v.end(), other.v.begin(), other.v.end(), res.v.begin());
        return res;
    }
};
vector<Node> st;

void build(int head, int l, int r)
{
    if (l == r)
    {
        st[head] = Node(arr[l]);
        return;
    }

    int mid = l + r >> 1;
    build(head << 1, l, mid);
    build(head << 1 | 1, mid + 1, r);
    st[head] = st[head << 1] + st[head << 1 | 1];
}

queue<int> pending;
void perform(int head, int l, int r, int u, int v, int i)
{
    if (l > v || r < u) return;
    if (u <= l && r <= v)
    {
        int &cur = st[head].ptr;
        while (cur < (int)st[head].v.size())
        {
            int val = st[head].v[cur].first;
            if (val > R[i] + T[i])
                break;
            int nxt = st[head].v[cur].second;
            if (dist[nxt] == oo)
            {
                pending.push(nxt);
                dist[nxt] = dist[i] + C[nxt];
            }
            cur++;
        }
        return;
    }

    int mid = l + r >> 1;
    perform(head << 1, l, mid, u, v, i);
    perform(head << 1 | 1, mid + 1, r, u, v, i);
}
void perform(int u, int v, int i) { perform(1, 1, m, u, v, i); }

void build()
{
    sort(proc.begin(), proc.end());
    for (int i = 1; i <= m; i++)
    {
        int idx = proc[i - 1].second;
        arr[i] = {L[idx] + T[idx] - 1, idx};
    }
    st.resize(4 * m + 1);
    build(1, 1, m);
}

void Dijkstra()
{
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    for (int i = 1; i <= m; i++)
        if (L[i] == 1)
            pq.push({dist[i] = C[i], i});

    while (!pq.empty())
    {
        int u = pq.top().second;
        pq.pop();

        int pos = upper_bound(proc.begin(), proc.end(), make_pair(R[u] - T[u], (int)1e9)) - proc.begin();
        if (pos != 0)
        {
            perform(1, pos, u);
            while (!pending.empty())
            {
                int v = pending.front();
                pending.pop();
                pq.push({dist[v], v});
            }
        }
    }
}

void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> T[i] >> L[i] >> R[i] >> C[i];
        proc.push_back({L[i] - T[i] - 1, i});
    }

    build();

    ll res = oo;
    Dijkstra();
    for (int i = 1; i <= m; i++)
        if (R[i] == n)
            res = min(res, dist[i]);

    cout << (res == oo ? -1 : res) << '\n';
}

컴파일 시 표준 에러 (stderr) 메시지

treatment.cpp: In function 'int main()':
treatment.cpp:19:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         freopen((name + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
treatment.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 30 / 30
• Subtask 4: 61 / 61