Submission #267108

#	Time	Username	Problem	Language	Result	Execution time	Memory
267108		shayan_p	Treatment Project (JOI20_treatment)	C++14	35 / 100	3053 ms	436032 KiB

treatment

// And you curse yourself for things you never done

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, int> pli;

const int maxn = 1e5 + 10;
const ll inf = 1e18 + 10;

int L[maxn], R[maxn], T[maxn], C[maxn];

const int MAXN2 = maxn * 40;

int VERTID, m;
vector<int> v[MAXN2];
bool mark[MAXN2];
ll dis[MAXN2];

void add_edge(int a, int b){
    v[a].PB(b);
}

struct Segment{
    vector<pii> v[4 * maxn];
    vector<int> L[4 * maxn], R[4 * maxn];
    function<bool(int, int)> f1, f2, f3; // tartib dim1 // tartib dim2 // sould I connect?
    int arr[maxn];
    void restart(function<bool(int, int)> _f1, function<bool(int, int)> _f2, function<bool(int, int)> _f3){
	f1 = _f1, f2 = _f2, f3 = _f3;
	/*	for(int i = 0; i < 4 * maxn; i++)
	    v[i].clear(), L[i].clear(), R[i].clear();
	iota(arr, arr + m, 0);
	sort(arr, arr + m, f1);
	build();*/

	
	iota(arr, arr + m, 0);
	sort(arr, arr + m, f1);

    }
    void build(int l = 0, int r = m, int id = 1){
	if(r-l == 1){
	    v[id].PB({arr[l], VERTID++});
	    return;
	}
	int mid = (l+r) >> 1;
	build(l, mid, 2*id);
	build(mid, r, 2*id+1);
	int pt1 = 0, pt2 = 0;
	while(pt1 + pt2 < sz(v[2*id]) + sz(v[2*id+1])){
	    L[id].PB(pt1), R[id].PB(pt2);
	    if(pt2 == sz(v[2*id+1]) || (pt1 != sz(v[2*id]) && f2(v[2*id][pt1].F, v[2*id+1][pt2].F)))
		v[id].PB({v[2*id][pt1++].F, VERTID++});
	    else
		v[id].PB({v[2*id+1][pt2++].F, VERTID++});
	}
	for(int i = 0; i < sz(v[id])-1; i++)
	    add_edge(v[id][i].S, v[id][i+1].S);
	for(pii p : v[id])
	    add_edge(p.S, p.F);
    }
    void add(int x, int l = 0, int r = m, int id = 1, int pos = -1){
	/*	if(id == 1){
	    int L = -1, R = m;
	    while(R-L > 1){
		int mid = (L+R) >> 1;
		if(f2(x, v[1][mid].F))
		    R = mid;
		else
		    L = mid;
	    }
	    pos = R;
	}
	if(pos >= sz(v[id]) || f3(x, arr[r-1]) == 0)
	    return;
	if(f3(x, arr[l])){
	    add_edge(x, v[id][pos].S);
	    return;
	}
	int mid = (l+r) >> 1;
	add(x, l, mid, 2*id, L[id][pos]);
	add(x, mid, r, 2*id+1, R[id][pos]);	    
	*/
	
	for(int i = 0; i < m; i++){
	    if(f3(x, i) && f2(x, i))
		add_edge(x, i);
	}
	for(int i = 0; i < m-1; i++){
	    if(f3(x, arr[i]))
		assert(f3(x, arr[i+1]));
	}
    }
};Segment seg;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();

    int n;
    cin >> n >> m;
    for(int i = 0; i < m; i++){
	cin >> T[i] >> L[i] >> R[i] >> C[i];
    }
    VERTID = m;
    int S = VERTID++, E = VERTID++;
    for(int i = 0; i < m; i++){
	if(L[i] == 1)
	    add_edge(S, i);
	if(R[i] == n)
	    add_edge(i, E); 
    }
    {
	auto A = [](int i){ return R[i] + T[i]; };
	auto B = [](int i){ return +T[i] + L[i] -1; };
	seg.restart([&](int i, int j){ return B(i) > B(j); }, [](int i, int j){ return T[i] <= T[j]; }, [&](int x, int S){ return A(x) >= B(S); });
	for(int i = 0; i < m; i++)
	    seg.add(i);
    }
    {
	auto A = [](int i){ return R[i] - T[i]; };
	auto B = [](int i){ return -T[i] + L[i] -1; };
	seg.restart([&](int i, int j){ return B(i) > B(j); }, [](int i, int j){ return T[i] >= T[j]; }, [&](int x, int S){ return A(x) >= B(S); });
	for(int i = 0; i < m; i++)
	    seg.add(i);
    }

    priority_queue<pli, vector<pli>, greater<pli> > pq;
    fill(dis, dis + VERTID, inf);
    pq.push({0, S});
    dis[S] = 0;
    
    while(sz(pq)){
	int u = pq.top().S;
	pq.pop();
	if(mark[u])
	    continue;
	mark[u] = 1;
	for(int y : v[u]){
	    ll x = dis[u] + (y < m ? C[y] : 0);
	    if(dis[y] > x)
		dis[y] = x, pq.push({dis[y], y});
	}
    }
    
    ll ans = dis[E];
    if(ans == inf)
	ans = -1;
    return cout << ans << endl, 0;
}

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