Submission #262123

#	Time	Username	Problem	Language	Result	Execution time	Memory
262123		Kastanda	Treatment Project (JOI20_treatment)	C++11	100 / 100	1287 ms	101744 KiB

treatment

// M
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100005;
int n, m, T[N], L[N], R[N], C[N], P[N], rev[N];
ll D[N];
vector < int > vec;
priority_queue < pair < ll , int > > Pq;
set < pair < int , int > > ST[2][N];
inline void Add(int w, int i, pair < int , int > val)
{
        for (; i < N; i += i & - i)
                ST[w][i].insert(val);
}
inline void Get(int w, int i, int ri)
{
        for (; i; i -= i & - i)
                while (ST[w][i].size() && ST[w][i].begin()->first <= ri)
                {
                        if (D[ST[w][i].begin()->second] == -1)
                                vec.push_back(ST[w][i].begin()->second);
                        ST[w][i].erase(ST[w][i].begin());
                }
}
int main()
{
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= m; i ++)
                scanf("%d%d%d%d", &T[i], &L[i], &R[i], &C[i]), R[i] ++;
        iota(P + 1, P + m + 1, 1);
        sort(P + 1, P + m + 1, [&](int i, int j){return T[i] < T[j];});
        for (int i = 1; i <= m; i ++)
                rev[P[i]] = i;

        for (int i = m; i; i --)
                Add(0, m - i + 1, make_pair(L[P[i]] + T[P[i]], P[i]));
        for (int i = 1; i <= m; i ++)
                Add(1, i, make_pair(L[P[i]] - T[P[i]], P[i]));

        memset(D, -1, sizeof(D));
        for (int i = 1; i <= m; i ++)
                if (L[i] == 1)
                        D[i] = C[i], Pq.push({-D[i], i});

        while (Pq.size())
        {
                ll d = - Pq.top().first;
                int v = Pq.top().second;
                Pq.pop();
                if (R[v] == n + 1)
                        return !printf("%lld\n", d);

                vec.clear();
                Get(0, m - rev[v], R[v] + T[v]);
                Get(1, rev[v] - 1, R[v] - T[v]);

                for (int u : vec)
                        if (D[u] == -1)
                                D[u] = D[v] + C[u], Pq.push({-D[u], u});
        }
        return !printf("-1\n");
}

Compilation message (stderr)

treatment.cpp: In function 'int main()':
treatment.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   28 |         scanf("%d%d", &n, &m);
      |         ~~~~~^~~~~~~~~~~~~~~~
treatment.cpp:30:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   30 |                 scanf("%d%d%d%d", &T[i], &L[i], &R[i], &C[i]), R[i] ++;
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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