oj.uz

Submission #945506

# Submission time Handle Problem Language Result Execution time Memory
945506 2024-03-14T02:17:52 Z guagua0407 Treatment Project (JOI20_treatment) C++17
100 / 100
 653 ms 58576 KB 
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

const int mxn=1e5+5;
const ll inf=1e18;
int t[mxn],L[mxn],R[mxn],c[mxn];
vector<int> adj[mxn];
vector<vector<int>> segtree1(mxn*4),segtree2(mxn*4);
vector<int> xs;
vector<bool> used(mxn);
vector<int> cur;

void update1(int id,int l=0,int r=xs.size()-1,int v=1){
    segtree1[v].push_back(id);
    if(l==r){
        return;
    }
    int mid=(l+r)/2;
    if(t[id]<=mid) update1(id,l,mid,v*2);
    else update1(id,mid+1,r,v*2+1);
}

void update2(int id,int l=0,int r=xs.size()-1,int v=1){
    segtree2[v].push_back(id);
    if(l==r){
        return;
    }
    int mid=(l+r)/2;
    if(t[id]<=mid) update2(id,l,mid,v*2);
    else update2(id,mid+1,r,v*2+1);
}

bool comp1(int a,int b){
    return L[a]+xs[t[a]]>L[b]+xs[t[b]];
}

void init1(int l=0,int r=xs.size()-1,int v=1){
    sort(all(segtree1[v]),comp1);
    if(l==r){
        return;
    }
    int mid=(l+r)/2;
    init1(l,mid,v*2);
    init1(mid+1,r,v*2+1);
}

bool comp2(int a,int b){
    return L[a]-xs[t[a]]>L[b]-xs[t[b]];
}

void init2(int l=0,int r=xs.size()-1,int v=1){
    sort(all(segtree2[v]),comp2);
    if(l==r){
        return;
    }
    int mid=(l+r)/2;
    init2(l,mid,v*2);
    init2(mid+1,r,v*2+1);
}

void query1(int tl,int tr,int id,int l=0,int r=xs.size()-1,int v=1){
    if(r<tl or tr<l){
        return;
    }
    if(tl<=l and r<=tr){
        while(!segtree1[v].empty() and R[id]+xs[t[id]]>=L[segtree1[v].back()]+xs[t[segtree1[v].back()]]-1){
            int u=segtree1[v].back();
            //cout<<"dasdasd "<<id<<' '<<u<<'\n';
            segtree1[v].pop_back();
            if(used[u]) continue;
            used[u]=true;
            cur.push_back(u);
        }
        return;
    }
    int mid=(l+r)/2;
    query1(tl,min(mid,tr),id,l,mid,v*2);
    query1(max(mid+1,tl),tr,id,mid+1,r,v*2+1);
}

void query2(int tl,int tr,int id,int l=0,int r=xs.size()-1,int v=1){
    if(r<tl or tr<l){
        return;
    }
    if(tl<=l and r<=tr){
        while(!segtree2[v].empty() and R[id]-xs[t[id]]>=L[segtree2[v].back()]-xs[t[segtree2[v].back()]]-1){
            int u=segtree2[v].back();
            segtree2[v].pop_back();
            if(used[u]) continue;
            used[u]=true;
            cur.push_back(u);
        }
        return ;
    }
    int mid=(l+r)/2;
    query2(tl,min(mid,tr),id,l,mid,v*2);
    query2(max(mid+1,tl),tr,id,mid+1,r,v*2+1);
}

vector<ll> dij(int n){
    vector<ll> d(n,inf);
    d[0]=0;
    used[0]=true;
    priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
    pq.push({0,0});
    while(!pq.empty()){
        auto tmp=pq.top();
        pq.pop();
        int v=tmp.s;
        if(tmp.f!=d[v]) continue;
        //cout<<d[v]<<' '<<v<<'\n';
        for(auto u:adj[v]){
            if(used[u]) continue;
            d[u]=d[v]+c[u];
            used[u]=true;
            pq.push({d[u],u});
        }
        if(v==0 or v==n-1) continue;
        cur.clear();
        query1(t[v],xs.size()-1,v);
        query2(0,t[v],v);
        for(auto u:cur){
            d[u]=d[v]+c[u];
            pq.push({d[u],u});
        }
    }
    return d;
}

int main() {_
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>t[i]>>L[i]>>R[i]>>c[i];
        xs.push_back(t[i]);
    }
    sort(all(xs));
    xs.resize(unique(all(xs))-xs.begin());
    for(int i=1;i<=m;i++){
        t[i]=lower_bound(all(xs),t[i])-xs.begin();
    }
    for(int i=1;i<=m;i++){
        update1(i);
        update2(i);
    }
    init1();
    init2();
    for(int i=1;i<=m;i++){
        if(L[i]==1) adj[0].push_back(i);
        if(R[i]==n) adj[i].push_back(m+1);
    }
    vector<ll> d=dij(m+2);
    cout<<(d[m+1]==inf?-1:d[m+1])<<'\n';
    return 0;
}
//maybe its multiset not set
//yeeorz
//laborz

Compilation message

treatment.cpp: In function 'void setIO(std::string)':
treatment.cpp:15:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
treatment.cpp:16:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 28628 KB Output is correct
2 Correct 73 ms 28792 KB Output is correct
3 Correct 67 ms 29556 KB Output is correct
4 Correct 82 ms 29068 KB Output is correct
5 Correct 68 ms 30352 KB Output is correct
6 Correct 63 ms 28628 KB Output is correct
7 Correct 59 ms 28628 KB Output is correct
8 Correct 50 ms 28628 KB Output is correct
9 Correct 49 ms 28584 KB Output is correct
10 Correct 52 ms 28676 KB Output is correct
11 Correct 81 ms 32216 KB Output is correct
12 Correct 83 ms 32476 KB Output is correct
13 Correct 79 ms 30552 KB Output is correct
14 Correct 84 ms 30548 KB Output is correct
15 Correct 81 ms 28520 KB Output is correct
16 Correct 74 ms 28628 KB Output is correct
17 Correct 72 ms 27860 KB Output is correct
18 Correct 81 ms 31444 KB Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 21596 KB Output is correct
2 Correct 6 ms 21592 KB Output is correct
3 Correct 6 ms 21592 KB Output is correct
4 Correct 6 ms 21592 KB Output is correct
5 Correct 6 ms 21596 KB Output is correct
6 Correct 6 ms 21596 KB Output is correct
7 Correct 7 ms 21596 KB Output is correct
8 Correct 6 ms 21596 KB Output is correct
9 Correct 7 ms 21596 KB Output is correct
10 Correct 6 ms 21596 KB Output is correct
11 Correct 6 ms 21596 KB Output is correct
12 Correct 6 ms 21536 KB Output is correct
13 Correct 6 ms 21592 KB Output is correct
14 Correct 7 ms 21852 KB Output is correct
15 Correct 5 ms 21596 KB Output is correct
16 Correct 6 ms 21596 KB Output is correct
17 Correct 6 ms 21596 KB Output is correct
18 Correct 6 ms 21644 KB Output is correct
19 Correct 6 ms 21596 KB Output is correct
20 Correct 18 ms 22872 KB Output is correct
21 Correct 19 ms 22872 KB Output is correct
22 Correct 17 ms 22620 KB Output is correct
23 Correct 19 ms 22620 KB Output is correct
24 Correct 23 ms 23152 KB Output is correct
25 Correct 20 ms 23128 KB Output is correct
26 Correct 18 ms 23132 KB Output is correct
27 Correct 16 ms 23160 KB Output is correct
28 Correct 20 ms 23132 KB Output is correct
29 Correct 18 ms 23128 KB Output is correct
30 Correct 14 ms 23132 KB Output is correct
31 Correct 14 ms 22964 KB Output is correct
32 Correct 21 ms 23388 KB Output is correct
33 Correct 20 ms 23328 KB Output is correct
34 Correct 20 ms 22952 KB Output is correct
35 Correct 21 ms 23388 KB Output is correct
36 Correct 20 ms 23384 KB Output is correct
37 Correct 20 ms 22876 KB Output is correct

Subtask #4
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 28628 KB Output is correct
2 Correct 73 ms 28792 KB Output is correct
3 Correct 67 ms 29556 KB Output is correct
4 Correct 82 ms 29068 KB Output is correct
5 Correct 68 ms 30352 KB Output is correct
6 Correct 63 ms 28628 KB Output is correct
7 Correct 59 ms 28628 KB Output is correct
8 Correct 50 ms 28628 KB Output is correct
9 Correct 49 ms 28584 KB Output is correct
10 Correct 52 ms 28676 KB Output is correct
11 Correct 81 ms 32216 KB Output is correct
12 Correct 83 ms 32476 KB Output is correct
13 Correct 79 ms 30552 KB Output is correct
14 Correct 84 ms 30548 KB Output is correct
15 Correct 81 ms 28520 KB Output is correct
16 Correct 74 ms 28628 KB Output is correct
17 Correct 72 ms 27860 KB Output is correct
18 Correct 81 ms 31444 KB Output is correct
19 Correct 7 ms 21596 KB Output is correct
20 Correct 6 ms 21592 KB Output is correct
21 Correct 6 ms 21592 KB Output is correct
22 Correct 6 ms 21592 KB Output is correct
23 Correct 6 ms 21596 KB Output is correct
24 Correct 6 ms 21596 KB Output is correct
25 Correct 7 ms 21596 KB Output is correct
26 Correct 6 ms 21596 KB Output is correct
27 Correct 7 ms 21596 KB Output is correct
28 Correct 6 ms 21596 KB Output is correct
29 Correct 6 ms 21596 KB Output is correct
30 Correct 6 ms 21536 KB Output is correct
31 Correct 6 ms 21592 KB Output is correct
32 Correct 7 ms 21852 KB Output is correct
33 Correct 5 ms 21596 KB Output is correct
34 Correct 6 ms 21596 KB Output is correct
35 Correct 6 ms 21596 KB Output is correct
36 Correct 6 ms 21644 KB Output is correct
37 Correct 6 ms 21596 KB Output is correct
38 Correct 18 ms 22872 KB Output is correct
39 Correct 19 ms 22872 KB Output is correct
40 Correct 17 ms 22620 KB Output is correct
41 Correct 19 ms 22620 KB Output is correct
42 Correct 23 ms 23152 KB Output is correct
43 Correct 20 ms 23128 KB Output is correct
44 Correct 18 ms 23132 KB Output is correct
45 Correct 16 ms 23160 KB Output is correct
46 Correct 20 ms 23132 KB Output is correct
47 Correct 18 ms 23128 KB Output is correct
48 Correct 14 ms 23132 KB Output is correct
49 Correct 14 ms 22964 KB Output is correct
50 Correct 21 ms 23388 KB Output is correct
51 Correct 20 ms 23328 KB Output is correct
52 Correct 20 ms 22952 KB Output is correct
53 Correct 21 ms 23388 KB Output is correct
54 Correct 20 ms 23384 KB Output is correct
55 Correct 20 ms 22876 KB Output is correct
56 Correct 452 ms 48904 KB Output is correct
57 Correct 490 ms 49288 KB Output is correct
58 Correct 467 ms 47020 KB Output is correct
59 Correct 450 ms 47248 KB Output is correct
60 Correct 376 ms 42964 KB Output is correct
61 Correct 452 ms 46804 KB Output is correct
62 Correct 442 ms 48724 KB Output is correct
63 Correct 508 ms 53664 KB Output is correct
64 Correct 494 ms 53760 KB Output is correct
65 Correct 106 ms 29820 KB Output is correct
66 Correct 368 ms 42980 KB Output is correct
67 Correct 493 ms 54240 KB Output is correct
68 Correct 383 ms 54196 KB Output is correct
69 Correct 391 ms 52920 KB Output is correct
70 Correct 506 ms 54448 KB Output is correct
71 Correct 402 ms 54192 KB Output is correct
72 Correct 396 ms 53964 KB Output is correct
73 Correct 542 ms 54452 KB Output is correct
74 Correct 353 ms 53972 KB Output is correct
75 Correct 253 ms 53972 KB Output is correct
76 Correct 537 ms 53740 KB Output is correct
77 Correct 636 ms 58576 KB Output is correct
78 Correct 607 ms 51660 KB Output is correct
79 Correct 653 ms 54740 KB Output is correct
80 Correct 576 ms 49524 KB Output is correct
81 Correct 474 ms 54444 KB Output is correct
82 Correct 559 ms 49188 KB Output is correct
83 Correct 595 ms 53404 KB Output is correct
84 Correct 574 ms 53688 KB Output is correct
85 Correct 568 ms 54224 KB Output is correct
86 Correct 528 ms 54440 KB Output is correct
87 Correct 531 ms 54400 KB Output is correct
88 Correct 563 ms 54140 KB Output is correct
89 Correct 533 ms 54368 KB Output is correct
90 Correct 576 ms 57296 KB Output is correct
91 Correct 561 ms 56092 KB Output is correct
92 Correct 522 ms 54424 KB Output is correct
93 Correct 592 ms 54400 KB Output is correct
94 Correct 539 ms 54480 KB Output is correct
95 Correct 559 ms 54224 KB Output is correct
96 Correct 591 ms 56944 KB Output is correct
97 Correct 552 ms 56692 KB Output is correct
98 Correct 544 ms 56684 KB Output is correct
99 Correct 573 ms 56548 KB Output is correct
100 Correct 529 ms 57552 KB Output is correct
101 Correct 600 ms 56540 KB Output is correct
102 Correct 540 ms 57600 KB Output is correct
103 Correct 531 ms 54820 KB Output is correct