oj.uz

Submission #1046874

# Submission time Handle Problem Language Result Execution time Memory
1046874 2024-08-07T05:35:04 Z 정희우(#11025) Treatment Project (JOI20_treatment) C++17
100 / 100
 448 ms 104644 KB 
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;
using lint = long long;
using vint = vector<int>;
using pii = pair<int,int>;

const int MAX_N=100010;
const lint INF=MAX_N*1e+9;

struct Obj
{
    lint t,l,r,c;
};

struct Comp
{
    int i;
    lint v;
    bool operator < (const Comp &o) const
    {
        return v>o.v;
    }
};

lint w;
int n;
Obj arr[MAX_N];
int tn;
vector<lint> pt;
priority_queue<Comp> pq;
lint dist[MAX_N];
vector<Comp> seg[2][MAX_N<<2];

void pushpq(int i,lint c)
{
    if(dist[i]<INF)return;
    dist[i]=c+arr[i].c;
    pq.push({i,dist[i]});
}

void update_(int i,int t,int s,int e,int x,int j,lint v)
{
    if(s>x || e<=x)
        return;
    seg[t][i].push_back({j,v});
    if(s==x && x+1==e)
        return;
    update_(i<<1,t,s,(s+e)>>1,x,j,v);
    update_(i<<1|1,t,(s+e)>>1,e,x,j,v);
}

void init_(int i,int t,int s,int e)
{
    sort(seg[t][i].begin(),seg[t][i].end());
    if(s+1==e)return;
    init_(i<<1,t,s,(s+e)>>1);
    init_(i<<1|1,t,(s+e)>>1,e);
}

void find_(int i,int t,int s,int e,int l,int r,lint v,lint c)
{
    if(s>=r || e<=l)return;
    if(l<=s && e<=r)
    {
        while(!seg[t][i].empty() && seg[t][i].back().v<=v)
        {
            pushpq(seg[t][i].back().i,c);
            seg[t][i].pop_back();
        }
        return;
    }
    find_(i<<1,t,s,(s+e)>>1,l,r,v,c);
    find_(i<<1|1,t,(s+e)>>1,e,l,r,v,c);
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> w >> n;
    for(int i=0;i<n;i++)
    {
        cin >> arr[i].t >> arr[i].l >> arr[i].r >> arr[i].c;arr[i].l--;
        pt.push_back(arr[i].t);
    }
    sort(pt.begin(),pt.end());
    tn=unique(pt.begin(),pt.end())-pt.begin();
    pt.resize(tn);
    fill(dist,dist+n,INF);
    for(int i=0;i<n;i++)
    {
        int x=lower_bound(pt.begin(),pt.end(),arr[i].t)-pt.begin();
        update_(1,0,0,tn,x,i,arr[i].l-arr[i].t);
        update_(1,1,0,tn,x,i,arr[i].l+arr[i].t);
        if(arr[i].l==0)
            pushpq(i,0);
    }
    for(int t=0;t<2;t++)
        init_(1,t,0,tn);
    while(!pq.empty())
    {
        auto p=pq.top();
        pq.pop();
        int x=lower_bound(pt.begin(),pt.end(),arr[p.i].t)-pt.begin();
        find_(1,0,0,tn,0,x+1,arr[p.i].r-arr[p.i].t,p.v);
        find_(1,1,0,tn,x,tn,arr[p.i].r+arr[p.i].t,p.v);
    }
    lint ans=INF;
    for(int i=0;i<n;i++)
        if(arr[i].r==w)
            ans=min(ans,dist[i]);
    if(ans==INF)
        cout << -1;
    else
        cout << ans;
    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 30416 KB Output is correct
2 Correct 40 ms 30272 KB Output is correct
3 Correct 40 ms 30828 KB Output is correct
4 Correct 39 ms 30784 KB Output is correct
5 Correct 44 ms 33028 KB Output is correct
6 Correct 46 ms 30416 KB Output is correct
7 Correct 46 ms 30204 KB Output is correct
8 Correct 33 ms 30080 KB Output is correct
9 Correct 33 ms 30212 KB Output is correct
10 Correct 34 ms 30204 KB Output is correct
11 Correct 51 ms 33140 KB Output is correct
12 Correct 50 ms 33200 KB Output is correct
13 Correct 49 ms 33012 KB Output is correct
14 Correct 51 ms 33264 KB Output is correct
15 Correct 44 ms 30200 KB Output is correct
16 Correct 44 ms 30204 KB Output is correct
17 Correct 41 ms 29436 KB Output is correct
18 Correct 44 ms 32336 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 21080 KB Output is correct
2 Correct 3 ms 21084 KB Output is correct
3 Correct 3 ms 21340 KB Output is correct
4 Correct 2 ms 21152 KB Output is correct
5 Correct 2 ms 21084 KB Output is correct
6 Correct 3 ms 21164 KB Output is correct
7 Correct 4 ms 21080 KB Output is correct
8 Correct 3 ms 21084 KB Output is correct
9 Correct 3 ms 21084 KB Output is correct
10 Correct 3 ms 21084 KB Output is correct
11 Correct 2 ms 21084 KB Output is correct
12 Correct 3 ms 21080 KB Output is correct
13 Correct 3 ms 21084 KB Output is correct
14 Correct 3 ms 21084 KB Output is correct
15 Correct 3 ms 21340 KB Output is correct
16 Correct 3 ms 21084 KB Output is correct
17 Correct 3 ms 21084 KB Output is correct
18 Correct 3 ms 21084 KB Output is correct
19 Correct 2 ms 21084 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 21080 KB Output is correct
2 Correct 3 ms 21084 KB Output is correct
3 Correct 3 ms 21340 KB Output is correct
4 Correct 2 ms 21152 KB Output is correct
5 Correct 2 ms 21084 KB Output is correct
6 Correct 3 ms 21164 KB Output is correct
7 Correct 4 ms 21080 KB Output is correct
8 Correct 3 ms 21084 KB Output is correct
9 Correct 3 ms 21084 KB Output is correct
10 Correct 3 ms 21084 KB Output is correct
11 Correct 2 ms 21084 KB Output is correct
12 Correct 3 ms 21080 KB Output is correct
13 Correct 3 ms 21084 KB Output is correct
14 Correct 3 ms 21084 KB Output is correct
15 Correct 3 ms 21340 KB Output is correct
16 Correct 3 ms 21084 KB Output is correct
17 Correct 3 ms 21084 KB Output is correct
18 Correct 3 ms 21084 KB Output is correct
19 Correct 2 ms 21084 KB Output is correct
20 Correct 11 ms 24156 KB Output is correct
21 Correct 13 ms 24152 KB Output is correct
22 Correct 11 ms 23644 KB Output is correct
23 Correct 11 ms 23828 KB Output is correct
24 Correct 17 ms 24668 KB Output is correct
25 Correct 14 ms 24668 KB Output is correct
26 Correct 14 ms 24588 KB Output is correct
27 Correct 11 ms 24412 KB Output is correct
28 Correct 13 ms 24668 KB Output is correct
29 Correct 12 ms 24620 KB Output is correct
30 Correct 9 ms 24668 KB Output is correct
31 Correct 9 ms 24408 KB Output is correct
32 Correct 13 ms 24756 KB Output is correct
33 Correct 13 ms 24924 KB Output is correct
34 Correct 12 ms 24412 KB Output is correct
35 Correct 13 ms 24668 KB Output is correct
36 Correct 13 ms 24668 KB Output is correct
37 Correct 12 ms 24408 KB Output is correct

Subtask #4
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 30416 KB Output is correct
2 Correct 40 ms 30272 KB Output is correct
3 Correct 40 ms 30828 KB Output is correct
4 Correct 39 ms 30784 KB Output is correct
5 Correct 44 ms 33028 KB Output is correct
6 Correct 46 ms 30416 KB Output is correct
7 Correct 46 ms 30204 KB Output is correct
8 Correct 33 ms 30080 KB Output is correct
9 Correct 33 ms 30212 KB Output is correct
10 Correct 34 ms 30204 KB Output is correct
11 Correct 51 ms 33140 KB Output is correct
12 Correct 50 ms 33200 KB Output is correct
13 Correct 49 ms 33012 KB Output is correct
14 Correct 51 ms 33264 KB Output is correct
15 Correct 44 ms 30200 KB Output is correct
16 Correct 44 ms 30204 KB Output is correct
17 Correct 41 ms 29436 KB Output is correct
18 Correct 44 ms 32336 KB Output is correct
19 Correct 3 ms 21080 KB Output is correct
20 Correct 3 ms 21084 KB Output is correct
21 Correct 3 ms 21340 KB Output is correct
22 Correct 2 ms 21152 KB Output is correct
23 Correct 2 ms 21084 KB Output is correct
24 Correct 3 ms 21164 KB Output is correct
25 Correct 4 ms 21080 KB Output is correct
26 Correct 3 ms 21084 KB Output is correct
27 Correct 3 ms 21084 KB Output is correct
28 Correct 3 ms 21084 KB Output is correct
29 Correct 2 ms 21084 KB Output is correct
30 Correct 3 ms 21080 KB Output is correct
31 Correct 3 ms 21084 KB Output is correct
32 Correct 3 ms 21084 KB Output is correct
33 Correct 3 ms 21340 KB Output is correct
34 Correct 3 ms 21084 KB Output is correct
35 Correct 3 ms 21084 KB Output is correct
36 Correct 3 ms 21084 KB Output is correct
37 Correct 2 ms 21084 KB Output is correct
38 Correct 11 ms 24156 KB Output is correct
39 Correct 13 ms 24152 KB Output is correct
40 Correct 11 ms 23644 KB Output is correct
41 Correct 11 ms 23828 KB Output is correct
42 Correct 17 ms 24668 KB Output is correct
43 Correct 14 ms 24668 KB Output is correct
44 Correct 14 ms 24588 KB Output is correct
45 Correct 11 ms 24412 KB Output is correct
46 Correct 13 ms 24668 KB Output is correct
47 Correct 12 ms 24620 KB Output is correct
48 Correct 9 ms 24668 KB Output is correct
49 Correct 9 ms 24408 KB Output is correct
50 Correct 13 ms 24756 KB Output is correct
51 Correct 13 ms 24924 KB Output is correct
52 Correct 12 ms 24412 KB Output is correct
53 Correct 13 ms 24668 KB Output is correct
54 Correct 13 ms 24668 KB Output is correct
55 Correct 12 ms 24408 KB Output is correct
56 Correct 326 ms 94288 KB Output is correct
57 Correct 328 ms 94664 KB Output is correct
58 Correct 309 ms 92628 KB Output is correct
59 Correct 365 ms 93100 KB Output is correct
60 Correct 238 ms 84672 KB Output is correct
61 Correct 314 ms 92820 KB Output is correct
62 Correct 332 ms 94032 KB Output is correct
63 Correct 362 ms 100084 KB Output is correct
64 Correct 347 ms 99968 KB Output is correct
65 Correct 55 ms 34428 KB Output is correct
66 Correct 233 ms 84692 KB Output is correct
67 Correct 342 ms 100292 KB Output is correct
68 Correct 308 ms 99848 KB Output is correct
69 Correct 256 ms 98500 KB Output is correct
70 Correct 379 ms 100288 KB Output is correct
71 Correct 304 ms 99524 KB Output is correct
72 Correct 280 ms 99780 KB Output is correct
73 Correct 373 ms 100376 KB Output is correct
74 Correct 222 ms 99528 KB Output is correct
75 Correct 207 ms 99420 KB Output is correct
76 Correct 363 ms 99320 KB Output is correct
77 Correct 409 ms 103880 KB Output is correct
78 Correct 373 ms 99008 KB Output is correct
79 Correct 448 ms 100852 KB Output is correct
80 Correct 373 ms 95936 KB Output is correct
81 Correct 310 ms 100548 KB Output is correct
82 Correct 378 ms 95432 KB Output is correct
83 Correct 413 ms 100008 KB Output is correct
84 Correct 431 ms 100292 KB Output is correct
85 Correct 372 ms 100544 KB Output is correct
86 Correct 368 ms 100636 KB Output is correct
87 Correct 382 ms 100444 KB Output is correct
88 Correct 392 ms 100800 KB Output is correct
89 Correct 393 ms 100908 KB Output is correct
90 Correct 398 ms 103872 KB Output is correct
91 Correct 399 ms 102380 KB Output is correct
92 Correct 375 ms 100560 KB Output is correct
93 Correct 403 ms 100800 KB Output is correct
94 Correct 418 ms 100784 KB Output is correct
95 Correct 405 ms 100768 KB Output is correct
96 Correct 394 ms 103712 KB Output is correct
97 Correct 405 ms 103940 KB Output is correct
98 Correct 397 ms 103624 KB Output is correct
99 Correct 398 ms 103728 KB Output is correct
100 Correct 393 ms 104644 KB Output is correct
101 Correct 403 ms 103620 KB Output is correct
102 Correct 407 ms 104064 KB Output is correct
103 Correct 396 ms 101060 KB Output is correct