oj.uz

Submission #1005703

# Submission time Handle Problem Language Result Execution time Memory
1005703 2024-06-22T19:58:09 Z Unforgettablepl Treatment Project (JOI20_treatment) C++17
100 / 100
 628 ms 129844 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
struct plan{
    int t,l,r,c;
    plan(int t,int l,int r,int c):t(t),l(l-1),r(r+1),c(c){}
    plan(int x):t(x),l(0),r(0),c(0){}
    bool operator<(const plan& other)const{
        return t-l<other.t-other.l;
    }
};

multiset<plan> tree[100001];

void add(int x,plan a){
    while(x<=100000){
        tree[x].insert(a);
        x+=x&-x;
    }
}

vector<plan> get(int x,int y){
    vector<plan> ans;
    while(x){
        while(tree[x].upper_bound(y)!=tree[x].end()){
            ans.emplace_back(*tree[x].upper_bound(y));
            tree[x].erase(tree[x].upper_bound(y));
        }
        x-=x&-x;
    }
    return ans;
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin >> n >> m;
    vector<plan> plans;
    priority_queue<pair<int,plan>> q;
    for(int i=1;i<=m;i++){
        int t,l,r,c;cin>>t>>l>>r>>c;
        if(l==1) q.emplace(-c,plan(t,l,r,c));
        else plans.emplace_back(t,l,r,c);
    }
    sort(plans.begin(),plans.end(),[](const plan &a,const plan& b){return a.t+a.l<b.t+b.l;});
    for(int i=0;i<plans.size();i++)add(i+1,plans[i]);
    while(!q.empty()){
        auto [dist,curr] = q.top();q.pop();
        if(curr.r==n+1){
            cout << -dist << '\n';
            return 0;
        }
        auto idx = lower_bound(plans.begin(),plans.end(),curr.r+curr.t,[](const plan &a,const int &b){return a.t+a.l<b;})-plans.begin();
        auto goodplans = get(idx,curr.t-curr.r);
        for(plan&i:goodplans)q.emplace(dist-i.c,i);
    }
    cout << "-1\n";
}

Compilation message

treatment.cpp: In function 'int32_t main()':
treatment.cpp:49:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<plan>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for(int i=0;i<plans.size();i++)add(i+1,plans[i]);
      |                 ~^~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 79804 KB Output is correct
2 Correct 205 ms 80060 KB Output is correct
3 Correct 206 ms 75440 KB Output is correct
4 Correct 219 ms 74340 KB Output is correct
5 Correct 188 ms 105576 KB Output is correct
6 Correct 311 ms 85276 KB Output is correct
7 Correct 312 ms 87364 KB Output is correct
8 Correct 151 ms 77256 KB Output is correct
9 Correct 145 ms 76764 KB Output is correct
10 Correct 162 ms 76992 KB Output is correct
11 Correct 179 ms 87616 KB Output is correct
12 Correct 194 ms 92280 KB Output is correct
13 Correct 325 ms 125860 KB Output is correct
14 Correct 318 ms 126632 KB Output is correct
15 Correct 393 ms 87780 KB Output is correct
16 Correct 356 ms 87220 KB Output is correct
17 Correct 322 ms 85828 KB Output is correct
18 Correct 191 ms 102028 KB Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 5156 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Correct 1 ms 5016 KB Output is correct
9 Correct 1 ms 4956 KB Output is correct
10 Correct 1 ms 4956 KB Output is correct
11 Correct 1 ms 4956 KB Output is correct
12 Correct 1 ms 4956 KB Output is correct
13 Correct 1 ms 4956 KB Output is correct
14 Correct 1 ms 4956 KB Output is correct
15 Correct 1 ms 4956 KB Output is correct
16 Correct 1 ms 4956 KB Output is correct
17 Correct 1 ms 4956 KB Output is correct
18 Correct 1 ms 4956 KB Output is correct
19 Correct 1 ms 4956 KB Output is correct
20 Correct 14 ms 9356 KB Output is correct
21 Correct 11 ms 9400 KB Output is correct
22 Correct 11 ms 9696 KB Output is correct
23 Correct 10 ms 9696 KB Output is correct
24 Correct 10 ms 9868 KB Output is correct
25 Correct 18 ms 9956 KB Output is correct
26 Correct 16 ms 9896 KB Output is correct
27 Correct 12 ms 10208 KB Output is correct
28 Correct 10 ms 9868 KB Output is correct
29 Correct 15 ms 9772 KB Output is correct
30 Correct 8 ms 9696 KB Output is correct
31 Correct 10 ms 9612 KB Output is correct
32 Correct 9 ms 10480 KB Output is correct
33 Correct 8 ms 10168 KB Output is correct
34 Correct 16 ms 10232 KB Output is correct
35 Correct 9 ms 10176 KB Output is correct
36 Correct 9 ms 10500 KB Output is correct
37 Correct 13 ms 10260 KB Output is correct

Subtask #4
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 79804 KB Output is correct
2 Correct 205 ms 80060 KB Output is correct
3 Correct 206 ms 75440 KB Output is correct
4 Correct 219 ms 74340 KB Output is correct
5 Correct 188 ms 105576 KB Output is correct
6 Correct 311 ms 85276 KB Output is correct
7 Correct 312 ms 87364 KB Output is correct
8 Correct 151 ms 77256 KB Output is correct
9 Correct 145 ms 76764 KB Output is correct
10 Correct 162 ms 76992 KB Output is correct
11 Correct 179 ms 87616 KB Output is correct
12 Correct 194 ms 92280 KB Output is correct
13 Correct 325 ms 125860 KB Output is correct
14 Correct 318 ms 126632 KB Output is correct
15 Correct 393 ms 87780 KB Output is correct
16 Correct 356 ms 87220 KB Output is correct
17 Correct 322 ms 85828 KB Output is correct
18 Correct 191 ms 102028 KB Output is correct
19 Correct 1 ms 4956 KB Output is correct
20 Correct 1 ms 5156 KB Output is correct
21 Correct 1 ms 4956 KB Output is correct
22 Correct 1 ms 4956 KB Output is correct
23 Correct 1 ms 4956 KB Output is correct
24 Correct 1 ms 4956 KB Output is correct
25 Correct 1 ms 4956 KB Output is correct
26 Correct 1 ms 5016 KB Output is correct
27 Correct 1 ms 4956 KB Output is correct
28 Correct 1 ms 4956 KB Output is correct
29 Correct 1 ms 4956 KB Output is correct
30 Correct 1 ms 4956 KB Output is correct
31 Correct 1 ms 4956 KB Output is correct
32 Correct 1 ms 4956 KB Output is correct
33 Correct 1 ms 4956 KB Output is correct
34 Correct 1 ms 4956 KB Output is correct
35 Correct 1 ms 4956 KB Output is correct
36 Correct 1 ms 4956 KB Output is correct
37 Correct 1 ms 4956 KB Output is correct
38 Correct 14 ms 9356 KB Output is correct
39 Correct 11 ms 9400 KB Output is correct
40 Correct 11 ms 9696 KB Output is correct
41 Correct 10 ms 9696 KB Output is correct
42 Correct 10 ms 9868 KB Output is correct
43 Correct 18 ms 9956 KB Output is correct
44 Correct 16 ms 9896 KB Output is correct
45 Correct 12 ms 10208 KB Output is correct
46 Correct 10 ms 9868 KB Output is correct
47 Correct 15 ms 9772 KB Output is correct
48 Correct 8 ms 9696 KB Output is correct
49 Correct 10 ms 9612 KB Output is correct
50 Correct 9 ms 10480 KB Output is correct
51 Correct 8 ms 10168 KB Output is correct
52 Correct 16 ms 10232 KB Output is correct
53 Correct 9 ms 10176 KB Output is correct
54 Correct 9 ms 10500 KB Output is correct
55 Correct 13 ms 10260 KB Output is correct
56 Correct 232 ms 76952 KB Output is correct
57 Correct 214 ms 77088 KB Output is correct
58 Correct 318 ms 85436 KB Output is correct
59 Correct 336 ms 86332 KB Output is correct
60 Correct 319 ms 80228 KB Output is correct
61 Correct 322 ms 85440 KB Output is correct
62 Correct 205 ms 78116 KB Output is correct
63 Correct 238 ms 80152 KB Output is correct
64 Correct 246 ms 80988 KB Output is correct
65 Correct 246 ms 83812 KB Output is correct
66 Correct 274 ms 80320 KB Output is correct
67 Correct 620 ms 84420 KB Output is correct
68 Correct 575 ms 82452 KB Output is correct
69 Correct 424 ms 82720 KB Output is correct
70 Correct 628 ms 85444 KB Output is correct
71 Correct 547 ms 82560 KB Output is correct
72 Correct 423 ms 84412 KB Output is correct
73 Correct 592 ms 84212 KB Output is correct
74 Correct 172 ms 80708 KB Output is correct
75 Correct 158 ms 80756 KB Output is correct
76 Correct 187 ms 92736 KB Output is correct
77 Correct 200 ms 88532 KB Output is correct
78 Correct 308 ms 129844 KB Output is correct
79 Correct 594 ms 83392 KB Output is correct
80 Correct 345 ms 90416 KB Output is correct
81 Correct 184 ms 80828 KB Output is correct
82 Correct 344 ms 89272 KB Output is correct
83 Correct 383 ms 89940 KB Output is correct
84 Correct 618 ms 82368 KB Output is correct
85 Correct 344 ms 87744 KB Output is correct
86 Correct 372 ms 87996 KB Output is correct
87 Correct 335 ms 88348 KB Output is correct
88 Correct 307 ms 91620 KB Output is correct
89 Correct 382 ms 86724 KB Output is correct
90 Correct 220 ms 95468 KB Output is correct
91 Correct 176 ms 81540 KB Output is correct
92 Correct 369 ms 81604 KB Output is correct
93 Correct 484 ms 82108 KB Output is correct
94 Correct 382 ms 90688 KB Output is correct
95 Correct 389 ms 86868 KB Output is correct
96 Correct 194 ms 87488 KB Output is correct
97 Correct 221 ms 105672 KB Output is correct
98 Correct 246 ms 104576 KB Output is correct
99 Correct 213 ms 94452 KB Output is correct
100 Correct 182 ms 91104 KB Output is correct
101 Correct 280 ms 126432 KB Output is correct
102 Correct 215 ms 96496 KB Output is correct
103 Correct 333 ms 85232 KB Output is correct