oj.uz

Submission #445919

# Submission time Handle Problem Language Result Execution time Memory
445919 2021-07-20T07:41:44 Z kig9981 Treatment Project (JOI20_treatment) C++17
0 / 100
 3000 ms 524292 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, x, y;
vector<tuple<int,int,int,int,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

# Verdict Execution time Memory Grader output
1 Correct 283 ms 82096 KB Output is correct
2 Correct 290 ms 82092 KB Output is correct
3 Execution timed out 3104 ms 235228 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 50244 KB Output is correct
2 Correct 28 ms 50344 KB Output is correct
3 Correct 26 ms 50220 KB Output is correct
4 Correct 27 ms 50320 KB Output is correct
5 Correct 26 ms 50296 KB Output is correct
6 Correct 27 ms 50220 KB Output is correct
7 Correct 27 ms 50252 KB Output is correct
8 Correct 32 ms 50312 KB Output is correct
9 Runtime error 633 ms 524292 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 50244 KB Output is correct
2 Correct 28 ms 50344 KB Output is correct
3 Correct 26 ms 50220 KB Output is correct
4 Correct 27 ms 50320 KB Output is correct
5 Correct 26 ms 50296 KB Output is correct
6 Correct 27 ms 50220 KB Output is correct
7 Correct 27 ms 50252 KB Output is correct
8 Correct 32 ms 50312 KB Output is correct
9 Runtime error 633 ms 524292 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 82096 KB Output is correct
2 Correct 290 ms 82092 KB Output is correct
3 Execution timed out 3104 ms 235228 KB Time limit exceeded
4 Halted 0 ms 0 KB -