oj.uz

Submission #1005702

# Submission time Handle Problem Language Result Execution time Memory
1005702 2024-06-22T19:56:41 Z Unforgettablepl Treatment Project (JOI20_treatment) C++17
4 / 100
 405 ms 129628 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<m;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);
        auto iter = plans.begin();
        for(plan&i:goodplans)q.emplace(dist-i.c,i);
    }
    cout << "-1\n";
}

Compilation message

treatment.cpp: In function 'int32_t main()':
treatment.cpp:58:14: warning: variable 'iter' set but not used [-Wunused-but-set-variable]
   58 |         auto iter = plans.begin();
      |              ^~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 84164 KB Output is correct
2 Correct 226 ms 83136 KB Output is correct
3 Correct 256 ms 91680 KB Output is correct
4 Correct 220 ms 92440 KB Output is correct
5 Correct 188 ms 107944 KB Output is correct
6 Correct 277 ms 88332 KB Output is correct
7 Correct 295 ms 88896 KB Output is correct
8 Correct 145 ms 79924 KB Output is correct
9 Correct 146 ms 80056 KB Output is correct
10 Correct 132 ms 80576 KB Output is correct
11 Correct 176 ms 92336 KB Output is correct
12 Correct 207 ms 94140 KB Output is correct
13 Correct 290 ms 129192 KB Output is correct
14 Correct 317 ms 129628 KB Output is correct
15 Correct 338 ms 89012 KB Output is correct
16 Correct 405 ms 90252 KB Output is correct
17 Correct 320 ms 88636 KB Output is correct
18 Correct 206 ms 104088 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 10076 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 10076 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 84164 KB Output is correct
2 Correct 226 ms 83136 KB Output is correct
3 Correct 256 ms 91680 KB Output is correct
4 Correct 220 ms 92440 KB Output is correct
5 Correct 188 ms 107944 KB Output is correct
6 Correct 277 ms 88332 KB Output is correct
7 Correct 295 ms 88896 KB Output is correct
8 Correct 145 ms 79924 KB Output is correct
9 Correct 146 ms 80056 KB Output is correct
10 Correct 132 ms 80576 KB Output is correct
11 Correct 176 ms 92336 KB Output is correct
12 Correct 207 ms 94140 KB Output is correct
13 Correct 290 ms 129192 KB Output is correct
14 Correct 317 ms 129628 KB Output is correct
15 Correct 338 ms 89012 KB Output is correct
16 Correct 405 ms 90252 KB Output is correct
17 Correct 320 ms 88636 KB Output is correct
18 Correct 206 ms 104088 KB Output is correct
19 Runtime error 4 ms 10076 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -