oj.uz

Submission #445947

# Submission time Handle Problem Language Result Execution time Memory
445947 2021-07-20T08:43:31 Z kig9981 Treatment Project (JOI20_treatment) C++17
4 / 100
 2504 ms 206612 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 p, int i)
{
	for(s+=SZ,e+=SZ;s<=e;s>>=1,e>>=1) {
		if(s&1) tree[s++].emplace(p,i);
		if(~e&1) tree[e--].emplace(p,i);
	}
}

void erase_tree(set<pair<int,int>> *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++].erase({p,i});
		if(~e&1) tree[e--].erase({p,i});
	}
}

void get_pos(set<pair<int,int>> *tree, int n, int l, int r)
{
	for(n+=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;
		if(--l==0 && r==N) {
			chk[i]=3;
			res=min(res,1LL*c);
			continue;
		}
		else if(l==0) {
			chk[i]=1;
			l=-r;
		}
		else if(r==N) {
			chk[i]=2;
			r=2*N-l;
		}
		x.push_back(l-N+t);
		x.push_back(r-N+t);
		y.push_back(l-t);
		y.push_back(r-t);
		tie(t,l,r,aa)=make_tuple(l-N+t,l-t,r-N+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,i);
			set_tree(ytree,y1,y2,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,x2,y1,y2); get_pos(ytree,y1,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,n);
			erase_tree(ytree,y1,y2,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
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 67952 KB Output is correct
2 Correct 222 ms 67960 KB Output is correct
3 Correct 1490 ms 152444 KB Output is correct
4 Correct 1468 ms 154756 KB Output is correct
5 Correct 204 ms 73568 KB Output is correct
6 Correct 187 ms 71568 KB Output is correct
7 Correct 169 ms 71016 KB Output is correct
8 Correct 139 ms 66580 KB Output is correct
9 Correct 142 ms 66696 KB Output is correct
10 Correct 136 ms 66296 KB Output is correct
11 Correct 2465 ms 206612 KB Output is correct
12 Correct 2440 ms 206388 KB Output is correct
13 Correct 1370 ms 148416 KB Output is correct
14 Correct 1331 ms 148356 KB Output is correct
15 Correct 765 ms 115764 KB Output is correct
16 Correct 759 ms 115908 KB Output is correct
17 Correct 688 ms 114928 KB Output is correct
18 Correct 2504 ms 206180 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 50252 KB Output is correct
2 Correct 28 ms 50304 KB Output is correct
3 Correct 26 ms 50252 KB Output is correct
4 Incorrect 27 ms 50268 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 50252 KB Output is correct
2 Correct 28 ms 50304 KB Output is correct
3 Correct 26 ms 50252 KB Output is correct
4 Incorrect 27 ms 50268 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 67952 KB Output is correct
2 Correct 222 ms 67960 KB Output is correct
3 Correct 1490 ms 152444 KB Output is correct
4 Correct 1468 ms 154756 KB Output is correct
5 Correct 204 ms 73568 KB Output is correct
6 Correct 187 ms 71568 KB Output is correct
7 Correct 169 ms 71016 KB Output is correct
8 Correct 139 ms 66580 KB Output is correct
9 Correct 142 ms 66696 KB Output is correct
10 Correct 136 ms 66296 KB Output is correct
11 Correct 2465 ms 206612 KB Output is correct
12 Correct 2440 ms 206388 KB Output is correct
13 Correct 1370 ms 148416 KB Output is correct
14 Correct 1331 ms 148356 KB Output is correct
15 Correct 765 ms 115764 KB Output is correct
16 Correct 759 ms 115908 KB Output is correct
17 Correct 688 ms 114928 KB Output is correct
18 Correct 2504 ms 206180 KB Output is correct
19 Correct 26 ms 50252 KB Output is correct
20 Correct 28 ms 50304 KB Output is correct
21 Correct 26 ms 50252 KB Output is correct
22 Incorrect 27 ms 50268 KB Output isn't correct
23 Halted 0 ms 0 KB -