oj.uz

답안 #446113

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
446113 2021-07-21T00:44:21 Z kig9981 치료 계획 (JOI20_treatment) C++17
9 / 100
 506 ms 43696 KB 
#include <bits/stdc++.h>
 
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
 
using namespace std;
 
const long long INF=0x3f3f3f3f3f3f3f3fLL;
const int SZ=1<<18;
vector<pair<int,int>> tree[2*SZ];
vector<int> P, x, y;
vector<tuple<int,int,int,int,int>> A;
long long dist1[100000], dist2[100000];
int chk[100000];

void set_tree(int s, int e, int p, int i)
{
	for(s+=SZ,e+=SZ;s<=e;s>>=1,e>>=1) {
		if(s&1) tree[s++].emplace_back(p,i);
		if(~e&1) tree[e--].emplace_back(p,i);
	}
}

void get_pos(int n, int l)
{
	for(n+=SZ;n;n>>=1) while(tree[n].size() && l<=tree[n].back().first) {
		P.push_back(tree[n].back().second);
		tree[n].pop_back();
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt","r",stdin));
	TEST(freopen("output.txt","w",stdout));
	TEST(freopen("debug.txt","w",stderr));
	int N, M;
	priority_queue<pair<long long,int>> Q;
	long long ans=INF;
	cin>>N>>M; A.resize(M);
	memset(dist1,0x3f,sizeof(dist1));
	memset(dist2,0x3f,sizeof(dist2));
	for(int i=0;i<M;i++) {
		auto &[t,l,r,aa,c]=A[i];
		cin>>t>>l>>r>>c;
		if(--l==0) chk[i]|=1;
		if(r==N) chk[i]|=2;
		x.push_back(l+t);
		x.push_back(r+t);
		y.push_back(l-t);
		y.push_back(r-t);
		tie(t,l,r,aa)=make_tuple(l+t,l-t,r+t,r-t);
	}
	sort(x.begin(),x.end()); x.resize(unique(x.begin(),x.end())-x.begin());
	sort(y.begin(),y.end()); y.resize(unique(y.begin(),y.end())-y.begin());
	for(int i=0;i<M;i++) {
		auto &[x1,y1,x2,y2,c]=A[i];
		x1=lower_bound(x.begin(),x.end(),x1)-x.begin();
		y1=lower_bound(y.begin(),y.end(),y1)-y.begin();
		x2=lower_bound(x.begin(),x.end(),x2)-x.begin();
		y2=lower_bound(y.begin(),y.end(),y2)-y.begin();
		if(chk[i]&1) Q.emplace(-(dist1[i]=c),i);
		else set_tree(x1,x2,-y1,i);
	}
	for(int i=2*SZ;--i;) sort(tree[i].begin(),tree[i].end());
	while(!Q.empty()) {
		auto[t,c]=Q.top();
		Q.pop();
		P.clear();
		auto[x1,y1,x2,y2,d]=A[c];
		get_pos(x2,-y2);
		for(auto n: P) if(dist1[n]==INF) {
			auto[x1,y1,x2,y2,d]=A[n];
			dist1[n]=dist1[c]+d;
			Q.emplace(-dist1[n],n);
		}
	}
	for(int i=2*SZ;--i;) tree[i].clear();
	for(int i=0;i<M;i++) {
		auto[x1,y1,x2,y2,c]=A[i];
		if(chk[i]&2) Q.emplace(-(dist2[i]=c),i);
		else set_tree(y1,y2,x2,i);
	}
	for(int i=2*SZ;--i;) sort(tree[i].begin(),tree[i].end());
	while(!Q.empty()) {
		auto[t,c]=Q.top();
		Q.pop();
		P.clear();
		auto[x1,y1,x2,y2,d]=A[c];
		get_pos(y1,x1);
		for(auto n: P) if(dist2[n]==INF) {
			auto[x1,y1,x2,y2,d]=A[n];
			dist2[n]=dist2[c]+d;
			Q.emplace(-dist2[n],n);
		}
	}
	for(int i=0;i<M;i++) ans=min(ans,dist1[i]+dist2[i]-get<4>(A[i]));
	cout<<(ans<INF ? ans:-1)<<'\n';
	return 0;
}

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 196 ms 25520 KB Output is correct
2 Correct 181 ms 25532 KB Output is correct
3 Correct 322 ms 32748 KB Output is correct
4 Correct 329 ms 33068 KB Output is correct
5 Correct 132 ms 24648 KB Output is correct
6 Correct 131 ms 22968 KB Output is correct
7 Correct 135 ms 22980 KB Output is correct
8 Correct 90 ms 21960 KB Output is correct
9 Correct 97 ms 22356 KB Output is correct
10 Correct 112 ms 22196 KB Output is correct
11 Correct 483 ms 43696 KB Output is correct
12 Correct 475 ms 41648 KB Output is correct
13 Correct 506 ms 38204 KB Output is correct
14 Correct 505 ms 38264 KB Output is correct
15 Correct 386 ms 32432 KB Output is correct
16 Correct 411 ms 32560 KB Output is correct
17 Correct 381 ms 31536 KB Output is correct
18 Correct 482 ms 41768 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 14156 KB Output is correct
2 Correct 12 ms 14156 KB Output is correct
3 Correct 11 ms 14196 KB Output is correct
4 Correct 12 ms 14172 KB Output is correct
5 Correct 12 ms 14156 KB Output is correct
6 Correct 12 ms 14132 KB Output is correct
7 Correct 12 ms 14156 KB Output is correct
8 Correct 11 ms 14152 KB Output is correct
9 Correct 12 ms 14100 KB Output is correct
10 Correct 11 ms 14156 KB Output is correct
11 Correct 11 ms 14156 KB Output is correct
12 Correct 11 ms 14200 KB Output is correct
13 Correct 11 ms 14200 KB Output is correct
14 Correct 11 ms 14172 KB Output is correct
15 Correct 11 ms 14200 KB Output is correct
16 Correct 12 ms 14156 KB Output is correct
17 Correct 12 ms 14156 KB Output is correct
18 Correct 11 ms 14156 KB Output is correct
19 Correct 11 ms 14156 KB Output is correct

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 14156 KB Output is correct
2 Correct 12 ms 14156 KB Output is correct
3 Correct 11 ms 14196 KB Output is correct
4 Correct 12 ms 14172 KB Output is correct
5 Correct 12 ms 14156 KB Output is correct
6 Correct 12 ms 14132 KB Output is correct
7 Correct 12 ms 14156 KB Output is correct
8 Correct 11 ms 14152 KB Output is correct
9 Correct 12 ms 14100 KB Output is correct
10 Correct 11 ms 14156 KB Output is correct
11 Correct 11 ms 14156 KB Output is correct
12 Correct 11 ms 14200 KB Output is correct
13 Correct 11 ms 14200 KB Output is correct
14 Correct 11 ms 14172 KB Output is correct
15 Correct 11 ms 14200 KB Output is correct
16 Correct 12 ms 14156 KB Output is correct
17 Correct 12 ms 14156 KB Output is correct
18 Correct 11 ms 14156 KB Output is correct
19 Correct 11 ms 14156 KB Output is correct
20 Correct 23 ms 15240 KB Output is correct
21 Correct 23 ms 15236 KB Output is correct
22 Incorrect 20 ms 14952 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# 결과 실행 시간 메모리 Grader output
1 Correct 196 ms 25520 KB Output is correct
2 Correct 181 ms 25532 KB Output is correct
3 Correct 322 ms 32748 KB Output is correct
4 Correct 329 ms 33068 KB Output is correct
5 Correct 132 ms 24648 KB Output is correct
6 Correct 131 ms 22968 KB Output is correct
7 Correct 135 ms 22980 KB Output is correct
8 Correct 90 ms 21960 KB Output is correct
9 Correct 97 ms 22356 KB Output is correct
10 Correct 112 ms 22196 KB Output is correct
11 Correct 483 ms 43696 KB Output is correct
12 Correct 475 ms 41648 KB Output is correct
13 Correct 506 ms 38204 KB Output is correct
14 Correct 505 ms 38264 KB Output is correct
15 Correct 386 ms 32432 KB Output is correct
16 Correct 411 ms 32560 KB Output is correct
17 Correct 381 ms 31536 KB Output is correct
18 Correct 482 ms 41768 KB Output is correct
19 Correct 11 ms 14156 KB Output is correct
20 Correct 12 ms 14156 KB Output is correct
21 Correct 11 ms 14196 KB Output is correct
22 Correct 12 ms 14172 KB Output is correct
23 Correct 12 ms 14156 KB Output is correct
24 Correct 12 ms 14132 KB Output is correct
25 Correct 12 ms 14156 KB Output is correct
26 Correct 11 ms 14152 KB Output is correct
27 Correct 12 ms 14100 KB Output is correct
28 Correct 11 ms 14156 KB Output is correct
29 Correct 11 ms 14156 KB Output is correct
30 Correct 11 ms 14200 KB Output is correct
31 Correct 11 ms 14200 KB Output is correct
32 Correct 11 ms 14172 KB Output is correct
33 Correct 11 ms 14200 KB Output is correct
34 Correct 12 ms 14156 KB Output is correct
35 Correct 12 ms 14156 KB Output is correct
36 Correct 11 ms 14156 KB Output is correct
37 Correct 11 ms 14156 KB Output is correct
38 Correct 23 ms 15240 KB Output is correct
39 Correct 23 ms 15236 KB Output is correct
40 Incorrect 20 ms 14952 KB Output isn't correct
41 Halted 0 ms 0 KB -