oj.uz

Submission #331992

# Submission time Handle Problem Language Result Execution time Memory
331992 2020-12-01T02:09:52 Z YJU Treatment Project (JOI20_treatment) C++14
100 / 100
 1867 ms 136480 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=1e5+5;
const ll K=350;
const ld pi=acos(-1);
const ll INF=(1LL<<60);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()

bool vis[N];

struct BIT{
	set<pll> B[N];
	void add(ll tox,pll ob){
		while(tox<N){
			B[tox].insert(ob);
			tox+=(tox&-tox);
		}
	}
	vector<ll> q(ll tox,ll lim){
		vector<ll> tmp;
		while(tox){
			while(SZ(B[tox])){
				pll i=*B[tox].begin();
				if(i.X>lim)break;
				if(!vis[i.Y])tmp.pb(i.Y);
				vis[i.Y]=1;
				B[tox].erase(B[tox].begin());
			}
			tox-=(tox&-tox);
		}
		return tmp;
	}
}t1,t2;

ll n,m,dis[N],C[N],T[N],L[N],R[N],ans=INF,id[N];
vector<ll> v[N],lis;

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

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>m;
	REP1(i,m){
		cin>>T[i]>>L[i]>>R[i]>>C[i];
		lis.pb(T[i]);
	}
	sort(lis.begin(),lis.end());
	lis.resize(unique(lis.begin(),lis.end())-lis.begin());
	REP1(i,m)id[i]=lwb(lis.begin(),lis.end(),T[i])-lis.begin()+1;
	REP1(i,m){
		if(L[i]==1)continue;
		t1.add(id[i],mp(L[i]-T[i]-1,i));
		t2.add(m-id[i]+1,mp(L[i]+T[i]-1,i));
	}
	/*REP1(i,m)REP1(j,m){
		if(id[i]>=id[j]&&R[i]-T[i]>=L[j]-T[j]-1){
			v[i].pb(j);
		}else if(id[i]<id[j]&&R[i]+T[i]>=L[j]+T[j]-1){
			v[i].pb(j);
		}
	}*/
	REP1(i,m){
		if(L[i]==1)pq.push(mp(dis[i]=C[i],i)),vis[i]=1;
		else dis[i]=INF;
	}
	while(SZ(pq)){
		ll x=pq.top().Y,y=pq.top().X;pq.pop();
		vector<ll> to1=t1.q(id[x],R[x]-T[x]),to2=t2.q(m-id[x],R[x]+T[x]);
		for(auto i:to1){
			vis[i]=1;
			pq.push(mp(dis[i]=y+C[i],i));
		}
		for(auto i:to2){
			vis[i]=1;
			pq.push(mp(dis[i]=y+C[i],i));
		}
	}
	REP1(i,m)if(R[i]==n)ans=min(ans,dis[i]);
	cout<<(ans==INF?-1:ans)<<"\n";
	return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 752 ms 133628 KB Output is correct
2 Correct 747 ms 133628 KB Output is correct
3 Correct 578 ms 106088 KB Output is correct
4 Correct 578 ms 105320 KB Output is correct
5 Correct 651 ms 134580 KB Output is correct
6 Correct 633 ms 133736 KB Output is correct
7 Correct 582 ms 133736 KB Output is correct
8 Correct 643 ms 132456 KB Output is correct
9 Correct 615 ms 133352 KB Output is correct
10 Correct 582 ms 133608 KB Output is correct
11 Correct 786 ms 136296 KB Output is correct
12 Correct 793 ms 136480 KB Output is correct
13 Correct 801 ms 135660 KB Output is correct
14 Correct 787 ms 135668 KB Output is correct
15 Correct 770 ms 133480 KB Output is correct
16 Correct 782 ms 133480 KB Output is correct
17 Correct 769 ms 132712 KB Output is correct
18 Correct 776 ms 135664 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12140 KB Output is correct
2 Correct 8 ms 12140 KB Output is correct
3 Correct 8 ms 12140 KB Output is correct
4 Correct 8 ms 12140 KB Output is correct
5 Correct 8 ms 12140 KB Output is correct
6 Correct 9 ms 12076 KB Output is correct
7 Correct 8 ms 12140 KB Output is correct
8 Correct 9 ms 12268 KB Output is correct
9 Correct 8 ms 12140 KB Output is correct
10 Correct 8 ms 12140 KB Output is correct
11 Correct 9 ms 12140 KB Output is correct
12 Correct 8 ms 12140 KB Output is correct
13 Correct 9 ms 12140 KB Output is correct
14 Correct 8 ms 12140 KB Output is correct
15 Correct 8 ms 12140 KB Output is correct
16 Correct 9 ms 12140 KB Output is correct
17 Correct 8 ms 12140 KB Output is correct
18 Correct 8 ms 12160 KB Output is correct
19 Correct 9 ms 12140 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12140 KB Output is correct
2 Correct 8 ms 12140 KB Output is correct
3 Correct 8 ms 12140 KB Output is correct
4 Correct 8 ms 12140 KB Output is correct
5 Correct 8 ms 12140 KB Output is correct
6 Correct 9 ms 12076 KB Output is correct
7 Correct 8 ms 12140 KB Output is correct
8 Correct 9 ms 12268 KB Output is correct
9 Correct 8 ms 12140 KB Output is correct
10 Correct 8 ms 12140 KB Output is correct
11 Correct 9 ms 12140 KB Output is correct
12 Correct 8 ms 12140 KB Output is correct
13 Correct 9 ms 12140 KB Output is correct
14 Correct 8 ms 12140 KB Output is correct
15 Correct 8 ms 12140 KB Output is correct
16 Correct 9 ms 12140 KB Output is correct
17 Correct 8 ms 12140 KB Output is correct
18 Correct 8 ms 12160 KB Output is correct
19 Correct 9 ms 12140 KB Output is correct
20 Correct 36 ms 17644 KB Output is correct
21 Correct 37 ms 17644 KB Output is correct
22 Correct 46 ms 19692 KB Output is correct
23 Correct 44 ms 19636 KB Output is correct
24 Correct 41 ms 18284 KB Output is correct
25 Correct 44 ms 19180 KB Output is correct
26 Correct 42 ms 19308 KB Output is correct
27 Correct 43 ms 19308 KB Output is correct
28 Correct 42 ms 18284 KB Output is correct
29 Correct 42 ms 19180 KB Output is correct
30 Correct 35 ms 19308 KB Output is correct
31 Correct 39 ms 19436 KB Output is correct
32 Correct 50 ms 19564 KB Output is correct
33 Correct 50 ms 19564 KB Output is correct
34 Correct 48 ms 19308 KB Output is correct
35 Correct 52 ms 19564 KB Output is correct
36 Correct 52 ms 19584 KB Output is correct
37 Correct 54 ms 19308 KB Output is correct

Subtask #4
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 752 ms 133628 KB Output is correct
2 Correct 747 ms 133628 KB Output is correct
3 Correct 578 ms 106088 KB Output is correct
4 Correct 578 ms 105320 KB Output is correct
5 Correct 651 ms 134580 KB Output is correct
6 Correct 633 ms 133736 KB Output is correct
7 Correct 582 ms 133736 KB Output is correct
8 Correct 643 ms 132456 KB Output is correct
9 Correct 615 ms 133352 KB Output is correct
10 Correct 582 ms 133608 KB Output is correct
11 Correct 786 ms 136296 KB Output is correct
12 Correct 793 ms 136480 KB Output is correct
13 Correct 801 ms 135660 KB Output is correct
14 Correct 787 ms 135668 KB Output is correct
15 Correct 770 ms 133480 KB Output is correct
16 Correct 782 ms 133480 KB Output is correct
17 Correct 769 ms 132712 KB Output is correct
18 Correct 776 ms 135664 KB Output is correct
19 Correct 9 ms 12140 KB Output is correct
20 Correct 8 ms 12140 KB Output is correct
21 Correct 8 ms 12140 KB Output is correct
22 Correct 8 ms 12140 KB Output is correct
23 Correct 8 ms 12140 KB Output is correct
24 Correct 9 ms 12076 KB Output is correct
25 Correct 8 ms 12140 KB Output is correct
26 Correct 9 ms 12268 KB Output is correct
27 Correct 8 ms 12140 KB Output is correct
28 Correct 8 ms 12140 KB Output is correct
29 Correct 9 ms 12140 KB Output is correct
30 Correct 8 ms 12140 KB Output is correct
31 Correct 9 ms 12140 KB Output is correct
32 Correct 8 ms 12140 KB Output is correct
33 Correct 8 ms 12140 KB Output is correct
34 Correct 9 ms 12140 KB Output is correct
35 Correct 8 ms 12140 KB Output is correct
36 Correct 8 ms 12160 KB Output is correct
37 Correct 9 ms 12140 KB Output is correct
38 Correct 36 ms 17644 KB Output is correct
39 Correct 37 ms 17644 KB Output is correct
40 Correct 46 ms 19692 KB Output is correct
41 Correct 44 ms 19636 KB Output is correct
42 Correct 41 ms 18284 KB Output is correct
43 Correct 44 ms 19180 KB Output is correct
44 Correct 42 ms 19308 KB Output is correct
45 Correct 43 ms 19308 KB Output is correct
46 Correct 42 ms 18284 KB Output is correct
47 Correct 42 ms 19180 KB Output is correct
48 Correct 35 ms 19308 KB Output is correct
49 Correct 39 ms 19436 KB Output is correct
50 Correct 50 ms 19564 KB Output is correct
51 Correct 50 ms 19564 KB Output is correct
52 Correct 48 ms 19308 KB Output is correct
53 Correct 52 ms 19564 KB Output is correct
54 Correct 52 ms 19584 KB Output is correct
55 Correct 54 ms 19308 KB Output is correct
56 Correct 885 ms 104132 KB Output is correct
57 Correct 887 ms 105448 KB Output is correct
58 Correct 1048 ms 129640 KB Output is correct
59 Correct 1123 ms 130024 KB Output is correct
60 Correct 1159 ms 132200 KB Output is correct
61 Correct 1036 ms 129580 KB Output is correct
62 Correct 877 ms 104040 KB Output is correct
63 Correct 942 ms 130920 KB Output is correct
64 Correct 928 ms 130920 KB Output is correct
65 Correct 814 ms 133736 KB Output is correct
66 Correct 1153 ms 131964 KB Output is correct
67 Correct 1184 ms 130860 KB Output is correct
68 Correct 850 ms 131560 KB Output is correct
69 Correct 695 ms 131560 KB Output is correct
70 Correct 1363 ms 130872 KB Output is correct
71 Correct 855 ms 131432 KB Output is correct
72 Correct 705 ms 131676 KB Output is correct
73 Correct 1374 ms 131048 KB Output is correct
74 Correct 692 ms 131432 KB Output is correct
75 Correct 595 ms 131560 KB Output is correct
76 Correct 1564 ms 134044 KB Output is correct
77 Correct 1615 ms 134172 KB Output is correct
78 Correct 1744 ms 132712 KB Output is correct
79 Correct 1867 ms 131560 KB Output is correct
80 Correct 1769 ms 130536 KB Output is correct
81 Correct 1401 ms 131688 KB Output is correct
82 Correct 1842 ms 129840 KB Output is correct
83 Correct 1814 ms 130780 KB Output is correct
84 Correct 1609 ms 130624 KB Output is correct
85 Correct 1424 ms 131688 KB Output is correct
86 Correct 1525 ms 131688 KB Output is correct
87 Correct 1598 ms 131560 KB Output is correct
88 Correct 1426 ms 131588 KB Output is correct
89 Correct 1427 ms 131688 KB Output is correct
90 Correct 1622 ms 134120 KB Output is correct
91 Correct 1546 ms 133924 KB Output is correct
92 Correct 1611 ms 131560 KB Output is correct
93 Correct 1801 ms 131588 KB Output is correct
94 Correct 1808 ms 131688 KB Output is correct
95 Correct 1725 ms 131668 KB Output is correct
96 Correct 1681 ms 133980 KB Output is correct
97 Correct 1574 ms 133708 KB Output is correct
98 Correct 1573 ms 134116 KB Output is correct
99 Correct 1583 ms 134132 KB Output is correct
100 Correct 1456 ms 122912 KB Output is correct
101 Correct 1665 ms 134112 KB Output is correct
102 Correct 1506 ms 135904 KB Output is correct
103 Correct 1600 ms 132120 KB Output is correct