Submission #578465

#	Time	Username	Problem	Language	Result	Execution time	Memory
578465		balbit	Treatment Project (JOI20_treatment)	C++14	100 / 100	243 ms	39556 KiB

treatment

#include <bits/stdc++.h>
using namespace std;
#define int ll
#define ll long long
#define pii pair<ll, ll>
#define f first
#define s second

#define SZ(x) (int)((x).size())
#define ALL(x) (x).begin(), (x).end()
#define pb push_back

#define MX(a,b) a =  max(a,b)
#define MN(a,b) a =  min(a,b)
#define FOR(i,a,b) for (int i = a; i<b; ++i)
#define REP(i,n) for (int i = 0; i<n; ++i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<"- "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
template<typename T> void _do(T && x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y){cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif // BALBIT


const int maxn = 3e5+5;
const int mod = 1e9+7;
const ll inf = 0x3f3f3f3f3f3f3f3f;

struct rect{
    int x,y,r,c,i;

    bool operator < (rect &R) {
        if (x != R.x) return x < R.x;
        return y < R.y;
    }
};

bool isbeg[maxn], isend[maxn]; // for each rectangle, is it the beg or end?????
bool done[maxn];
ll dst[maxn];

pii s[maxn*4]; // minimum y position, index (in segment tree!!!!!)

void MO(int p, pii v, int o = 1, int l = 0, int r = maxn-1) {
    if( l > p || r < p) return;
    if( l == r) {
        s[o] = v;
        return;
    }
    int mid = (l+r)/2;
    MO(p,v,o*2,l,mid); MO(p,v,o*2+1,mid+1,r);
    s[o] = min(s[o*2],s[o*2+1]);
}

pii QU(int L, int R, int o=1, int l=0, int r=maxn-1) {
    if (l > R || r < L) return {inf,  -1};
    if (l >= L && r <= R) return s[o];
    int  mid = (l+r)/2;
    return min(QU(L,R,o*2,l,mid), QU(L,R,o*2+1,mid+1,r));
}

void build(){
    fill(s, s+maxn*4, pii{inf,-1});
}

ll get(vector<rect> v) {
    for (rect &R : v) {
        bug(R.x,R.y,R.r,R.c,R.i);
        bug(isbeg[R.i]);
        bug(isend[R.i]);
    }

//    sort(ALL(v));

    memset(dst, 0x3f, sizeof dst);
    int n = SZ(v);

    priority_queue<pii, vector<pii>, greater<pii> >pq;

    vector<pair<pii, int> > pts;
    build();

    for (rect &R : v) {
        if (isbeg[R.i]) {
            dst[R.i]=R.c;
            pq.push({dst[R.i], R.i});
        }else{
            pts.pb({{R.x, R.y}, R.i});
        }
    }

    sort(ALL(pts));
    for (rect &R : v) {
        if (isbeg[R.i]) continue;
        int meat = lower_bound(ALL(pts), make_pair(make_pair(R.x, R.y), R.i)) - pts.begin();
        MO(meat, {R.y, meat});
    }

    ll re = inf;

    while (!pq.empty()) {
        int me = pq.top().s; ll w = pq.top().f; pq.pop();
        if (dst[me] != w) continue;
        if (isend[me]) {
            MN(re, dst[me]);
        }
        pair<pii, int> moo = make_pair(make_pair(v[me].x + v[me].r + 1, v[me].y + v[me].r + 1), 1000000);
        int upto = upper_bound(ALL(pts), moo) - pts.begin() - 1;
        pii hi = QU(0,upto);
        while (hi.s != -1) {
            if (hi.f > v[me].y + v[me].r + 1) break;
//            bug(hi.s);
            int who = pts[hi.s].s;
            bug(me, who);
            dst[who] = v[who].c + dst[me];
            pq.push({dst[who], who});
            MO(hi.s, {inf, -1});
            hi = QU(0, upto);
        }
    }
    if (re == inf) return -1;
    return re;
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    bug(1,2);

    vector<rect> go;
    int n,m; cin>>n>>m;
    REP(i,m) {
        int t,l,r,c; cin>>t>>l>>r>>c;
        --l; --r;
        isbeg[i] = l == 0;
        isend[i] = r == n-1;
        go.pb({l+t, l-t,r-l,c,i});
    }

    ll re =get(go);
    cout<<re<<endl;

}

/*
10 5
1 8 10 30
1 1 6 50
2 7 7 100
3 5 7 11
2 8 8 11



7 6 10 4
4 1 3 1
*/

Compilation message (stderr)

treatment.cpp: In function 'long long int get(std::vector<rect>)':
treatment.cpp:71:16: warning: unused variable 'R' [-Wunused-variable]
   71 |     for (rect &R : v) {
      |                ^
treatment.cpp:80:9: warning: unused variable 'n' [-Wunused-variable]
   80 |     int n = SZ(v);
      |         ^

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