oj.uz

Submission #445949

# Submission time Handle Problem Language Result Execution time Memory
445949 2021-07-20T08:47:29 Z kig9981 Treatment Project (JOI20_treatment) C++17
4 / 100
 2416 ms 203656 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,y2,i);
			set_tree(ytree,y1,y2,x1,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,y1,y2); get_pos(ytree,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,y2,n);
			erase_tree(ytree,y1,y2,x1,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 233 ms 68156 KB Output is correct
2 Correct 219 ms 67964 KB Output is correct
3 Correct 1517 ms 152348 KB Output is correct
4 Correct 1490 ms 152632 KB Output is correct
5 Correct 211 ms 70384 KB Output is correct
6 Correct 180 ms 68572 KB Output is correct
7 Correct 171 ms 68168 KB Output is correct
8 Correct 140 ms 63460 KB Output is correct
9 Correct 143 ms 63656 KB Output is correct
10 Correct 134 ms 63280 KB Output is correct
11 Correct 2405 ms 203652 KB Output is correct
12 Correct 2402 ms 203352 KB Output is correct
13 Correct 1307 ms 145532 KB Output is correct
14 Correct 1307 ms 145524 KB Output is correct
15 Correct 754 ms 112688 KB Output is correct
16 Correct 728 ms 112944 KB Output is correct
17 Correct 702 ms 112636 KB Output is correct
18 Correct 2416 ms 203656 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 50440 KB Output is correct
2 Incorrect 26 ms 50324 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 50440 KB Output is correct
2 Incorrect 26 ms 50324 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 68156 KB Output is correct
2 Correct 219 ms 67964 KB Output is correct
3 Correct 1517 ms 152348 KB Output is correct
4 Correct 1490 ms 152632 KB Output is correct
5 Correct 211 ms 70384 KB Output is correct
6 Correct 180 ms 68572 KB Output is correct
7 Correct 171 ms 68168 KB Output is correct
8 Correct 140 ms 63460 KB Output is correct
9 Correct 143 ms 63656 KB Output is correct
10 Correct 134 ms 63280 KB Output is correct
11 Correct 2405 ms 203652 KB Output is correct
12 Correct 2402 ms 203352 KB Output is correct
13 Correct 1307 ms 145532 KB Output is correct
14 Correct 1307 ms 145524 KB Output is correct
15 Correct 754 ms 112688 KB Output is correct
16 Correct 728 ms 112944 KB Output is correct
17 Correct 702 ms 112636 KB Output is correct
18 Correct 2416 ms 203656 KB Output is correct
19 Correct 27 ms 50440 KB Output is correct
20 Incorrect 26 ms 50324 KB Output isn't correct
21 Halted 0 ms 0 KB -