oj.uz

답안 #445921

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
445921 2021-07-20T07:43:03 Z kig9981 치료 계획 (JOI20_treatment) C++17
5 / 100
 3000 ms 239184 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;
set<pair<int,int>> xtree[2*SZ], ytree[2*SZ];
vector<int> P;
vector<long long> x, y;
vector<tuple<long long,long long,long long,long long,int>> A;
long long dist[100000];
int chk[100000];

void set_tree(set<pair<int,int>> *tree, int s, int e, int p1, int p2, int i)
{
	for(s+=SZ,e+=SZ;s<=e;s>>=1,e>>=1) {
		if(s&1) {
			tree[s].emplace(p1,i);
			tree[s++].emplace(p2,i);
		}
		if(~e&1) {
			tree[e].emplace(p1,i);
			tree[e--].emplace(p2,i);
		}
	}
}

void erase_tree(set<pair<int,int>> *tree, int s, int e, int p1, int p2, int i)
{
	for(s+=SZ,e+=SZ;s<=e;s>>=1,e>>=1) {
		if(s&1) {
			tree[s].erase({p1,i});
			tree[s++].erase({p2,i});
		}
		if(~e&1) {
			tree[e].erase({p1,i});
			tree[e--].erase({p2,i});
		}
	}
}

void get_pos(set<pair<int,int>> *tree, int s, int e, int l, int r)
{
	for(int n=s+SZ;n;n>>=1) for(auto L=tree[n].lower_bound({l,0}),R=tree[n].lower_bound({r+1,0});L!=R;++L) P.push_back(L->second);
	for(int n=e+SZ;n;n>>=1) for(auto L=tree[n].lower_bound({l,0}),R=tree[n].lower_bound({r+1,0});L!=R;++L) P.push_back(L->second);
}
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, res=INF;
	cin>>N>>M; A.resize(M);
	memset(dist,0x3f,sizeof(dist));
	for(int i=0;i<M;i++) {
		auto &[t,l,r,aa,c]=A[i];
		cin>>t>>l>>r>>c; --l;
		if(l==0 && r==N) {
			chk[i]=3;
			res=min(res,1LL*c);
		}
		else if(l==0) {
			chk[i]=1;
			l=-N;
		}
		else if(r==N) {
			chk[i]=2;
			r=2*N;
		}
		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(-(dist[i]=c),i);
		else if(chk[i]!=3) {
			set_tree(xtree,x1,x2,y1,y2,i);
			set_tree(ytree,y1,y2,x1,x2,i);
		}
	}
	while(!Q.empty()) {
		auto[t,c]=Q.top();
		Q.pop();
		P.clear();
		auto[x1,y1,x2,y2,d]=A[c];
		get_pos(xtree,x1,x2,y1,y2); get_pos(ytree,y1,y2,x1,x2);
		for(auto n: P) if(dist[n]==INF) {
			auto[x1,y1,x2,y2,d]=A[n];
			dist[n]=dist[c]+d;
			erase_tree(xtree,x1,x2,y1,y2,n);
			erase_tree(ytree,y1,y2,x1,x2,n);
			Q.emplace(-dist[n],n);
		}
	}
	ans=res;
	for(int i=0;i<M;i++) if(chk[i]==2) ans=min(ans,dist[i]);
	cout<<(ans<INF ? ans:-1)<<'\n';
	return 0;
}

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 291 ms 86636 KB Output is correct
2 Correct 280 ms 86140 KB Output is correct
3 Execution timed out 3094 ms 239184 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 50252 KB Output is correct
2 Correct 26 ms 50244 KB Output is correct
3 Correct 27 ms 50340 KB Output is correct
4 Correct 27 ms 50252 KB Output is correct
5 Correct 27 ms 50336 KB Output is correct
6 Correct 28 ms 50316 KB Output is correct
7 Correct 27 ms 50288 KB Output is correct
8 Correct 27 ms 50244 KB Output is correct
9 Correct 27 ms 50336 KB Output is correct
10 Correct 28 ms 50364 KB Output is correct
11 Correct 27 ms 50292 KB Output is correct
12 Correct 26 ms 50252 KB Output is correct
13 Correct 26 ms 50256 KB Output is correct
14 Correct 28 ms 50244 KB Output is correct
15 Correct 26 ms 50252 KB Output is correct
16 Correct 27 ms 50268 KB Output is correct
17 Correct 26 ms 50360 KB Output is correct
18 Correct 27 ms 50284 KB Output is correct
19 Correct 28 ms 50252 KB Output is correct

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 50252 KB Output is correct
2 Correct 26 ms 50244 KB Output is correct
3 Correct 27 ms 50340 KB Output is correct
4 Correct 27 ms 50252 KB Output is correct
5 Correct 27 ms 50336 KB Output is correct
6 Correct 28 ms 50316 KB Output is correct
7 Correct 27 ms 50288 KB Output is correct
8 Correct 27 ms 50244 KB Output is correct
9 Correct 27 ms 50336 KB Output is correct
10 Correct 28 ms 50364 KB Output is correct
11 Correct 27 ms 50292 KB Output is correct
12 Correct 26 ms 50252 KB Output is correct
13 Correct 26 ms 50256 KB Output is correct
14 Correct 28 ms 50244 KB Output is correct
15 Correct 26 ms 50252 KB Output is correct
16 Correct 27 ms 50268 KB Output is correct
17 Correct 26 ms 50360 KB Output is correct
18 Correct 27 ms 50284 KB Output is correct
19 Correct 28 ms 50252 KB Output is correct
20 Correct 76 ms 57388 KB Output is correct
21 Correct 74 ms 57356 KB Output is correct
22 Correct 59 ms 54740 KB Output is correct
23 Correct 47 ms 54668 KB Output is correct
24 Correct 84 ms 58780 KB Output is correct
25 Incorrect 69 ms 56904 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# 결과 실행 시간 메모리 Grader output
1 Correct 291 ms 86636 KB Output is correct
2 Correct 280 ms 86140 KB Output is correct
3 Execution timed out 3094 ms 239184 KB Time limit exceeded
4 Halted 0 ms 0 KB -