oj.uz

Submission #267108

# Submission time Handle Problem Language Result Execution time Memory
267108 2020-08-15T20:19:57 Z shayan_p Treatment Project (JOI20_treatment) C++14
35 / 100
 3000 ms 436032 KB 
// 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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3053 ms 436032 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 122488 KB Output is correct
2 Correct 83 ms 122612 KB Output is correct
3 Correct 82 ms 122488 KB Output is correct
4 Correct 81 ms 122484 KB Output is correct
5 Correct 82 ms 122488 KB Output is correct
6 Correct 82 ms 122488 KB Output is correct
7 Correct 83 ms 122488 KB Output is correct
8 Correct 83 ms 122544 KB Output is correct
9 Correct 83 ms 122488 KB Output is correct
10 Correct 83 ms 122488 KB Output is correct
11 Correct 84 ms 122488 KB Output is correct
12 Correct 82 ms 122488 KB Output is correct
13 Correct 82 ms 122464 KB Output is correct
14 Correct 84 ms 122488 KB Output is correct
15 Correct 83 ms 122488 KB Output is correct
16 Correct 84 ms 122488 KB Output is correct
17 Correct 82 ms 122488 KB Output is correct
18 Correct 82 ms 122488 KB Output is correct
19 Correct 84 ms 122492 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 122488 KB Output is correct
2 Correct 83 ms 122612 KB Output is correct
3 Correct 82 ms 122488 KB Output is correct
4 Correct 81 ms 122484 KB Output is correct
5 Correct 82 ms 122488 KB Output is correct
6 Correct 82 ms 122488 KB Output is correct
7 Correct 83 ms 122488 KB Output is correct
8 Correct 83 ms 122544 KB Output is correct
9 Correct 83 ms 122488 KB Output is correct
10 Correct 83 ms 122488 KB Output is correct
11 Correct 84 ms 122488 KB Output is correct
12 Correct 82 ms 122488 KB Output is correct
13 Correct 82 ms 122464 KB Output is correct
14 Correct 84 ms 122488 KB Output is correct
15 Correct 83 ms 122488 KB Output is correct
16 Correct 84 ms 122488 KB Output is correct
17 Correct 82 ms 122488 KB Output is correct
18 Correct 82 ms 122488 KB Output is correct
19 Correct 84 ms 122492 KB Output is correct
20 Correct 1124 ms 194264 KB Output is correct
21 Correct 1080 ms 194424 KB Output is correct
22 Correct 863 ms 124536 KB Output is correct
23 Correct 857 ms 124408 KB Output is correct
24 Correct 897 ms 172320 KB Output is correct
25 Correct 732 ms 158124 KB Output is correct
26 Correct 675 ms 156400 KB Output is correct
27 Correct 701 ms 163448 KB Output is correct
28 Correct 909 ms 171616 KB Output is correct
29 Correct 754 ms 157552 KB Output is correct
30 Correct 729 ms 161880 KB Output is correct
31 Correct 695 ms 165868 KB Output is correct
32 Correct 1156 ms 189808 KB Output is correct
33 Correct 1151 ms 232196 KB Output is correct
34 Correct 1059 ms 187712 KB Output is correct
35 Correct 1091 ms 189948 KB Output is correct
36 Correct 1163 ms 231952 KB Output is correct
37 Correct 1053 ms 187552 KB Output is correct

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3053 ms 436032 KB Time limit exceeded
2 Halted 0 ms 0 KB -