Submission #1090882

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090882		phong	Treatment Project (JOI20_treatment)	C++17	100 / 100	84 ms	14544 KiB

treatment

#include<bits/stdc++.h>
#define ll long long
const int nmax = 1e5 + 5, N = 1e5;
const ll oo = 1e18 + 5, base = 311;
const int lg = 17,mod = 1e9 +7;
#define pii pair<ll, ll>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;
int n, m;
struct node{
    ll t, l, r, c;
}a[nmax];
ll dp[nmax];
ll tree[nmax << 2][2];
    priority_queue<pii, vector<pii>, greater<pii>> q;

void build(int id, int l, int r){
    if(l == r){
        if(dp[l] == oo){
            tree[id][0] = a[l].l - a[l].t;
            tree[id][1] = a[l].l + a[l].t;
        }
        else tree[id][0] =tree[id][1] = oo;
        return;
    }
    int mid = r+ l >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    for(int e = 0; e < 2; ++e) tree[id][e] = min(tree[id << 1][e], tree[id << 1 | 1][e]);
}

void update(int id, int l, int r, int u, int v,ll val, int k, int idx){
    if(l > v || r < u || u > v)return;
    if(tree[id][idx] > k) return;
    if(l == r){
        dp[l] = val + a[l].c;
    //        cout << l << ' ' << dp[l] << endl;
        q.push({dp[l], l});
        tree[id][0] = tree[id][1] = oo;
        return;
    }
    int mid = r+ l >> 1;
    update(id << 1, l, mid, u,v ,val, k, idx);
    update(id << 1 | 1, mid + 1, r, u, v,val, k, idx);
    for(int e = 0; e < 2; ++e) tree[id][e] = min(tree[id << 1][e], tree[id << 1 | 1][e]);
}
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen("ROBOT.inp", "r", stdin);
//    freopen("ROBOT.out", "w", stdout);
    cin >> n >> m;
    for(int i = 1; i <= m; ++i) cin >> a[i].t >> a[i].l >> a[i].r >> a[i].c;
    sort(a + 1, a + 1 + m, [](node a, node b){
         return a.t < b.t;
         });
    for(int i = 1; i <= m; ++i) dp[i] = oo;
    for(int i = 1; i <= m; ++i){
        if(a[i].l == 1){

            dp[i] = a[i].c;
            q.push({dp[i], i});
        }
    }
    build(1, 1, m);
    while(q.size()){
        pii tmp = q.top();q.pop();
        int u = tmp.se;
        ll val = tmp.fi;
        update(1, 1, m, 1, u - 1, val, a[u].r - a[u].t + 1, 0);
        update(1, 1, m, u + 1, n, val, a[u].r + a[u].t + 1, 1);
    }
    ll ans = oo;
    for(int i = 1; i <= m; ++i){
        if(a[i].r == n){
            ans = min(ans, dp[i]);
        }
    }
    if(ans == oo) cout << -1;
    else cout << ans;
}
/*
3 3

899
*/

Compilation message (stderr)

treatment.cpp: In function 'void build(int, int, int)':
treatment.cpp:29:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |     int mid = r+ l >> 1;
      |               ~^~~
treatment.cpp: In function 'void update(int, int, int, int, int, long long int, int, int)':
treatment.cpp:45:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |     int mid = r+ l >> 1;
      |               ~^~~
treatment.cpp: At global scope:
treatment.cpp:50:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   50 | main(){
      | ^~~~

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