oj.uz

Submission #445989

# Submission time Handle Problem Language Result Execution time Memory
445989 2021-07-20T10:46:47 Z kig9981 Treatment Project (JOI20_treatment) C++17
4 / 100
 2472 ms 204864 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,x.size());
		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 242 ms 71080 KB Output is correct
2 Correct 227 ms 69828 KB Output is correct
3 Correct 1528 ms 154148 KB Output is correct
4 Correct 1498 ms 153776 KB Output is correct
5 Correct 197 ms 71632 KB Output is correct
6 Correct 190 ms 69688 KB Output is correct
7 Correct 173 ms 69384 KB Output is correct
8 Correct 143 ms 64740 KB Output is correct
9 Correct 145 ms 64816 KB Output is correct
10 Correct 138 ms 64512 KB Output is correct
11 Correct 2401 ms 204656 KB Output is correct
12 Correct 2472 ms 204576 KB Output is correct
13 Correct 1394 ms 146572 KB Output is correct
14 Correct 1347 ms 146444 KB Output is correct
15 Correct 752 ms 113952 KB Output is correct
16 Correct 760 ms 114116 KB Output is correct
17 Correct 702 ms 113996 KB Output is correct
18 Correct 2396 ms 204864 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 50224 KB Output is correct
2 Incorrect 31 ms 50252 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 50224 KB Output is correct
2 Incorrect 31 ms 50252 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 71080 KB Output is correct
2 Correct 227 ms 69828 KB Output is correct
3 Correct 1528 ms 154148 KB Output is correct
4 Correct 1498 ms 153776 KB Output is correct
5 Correct 197 ms 71632 KB Output is correct
6 Correct 190 ms 69688 KB Output is correct
7 Correct 173 ms 69384 KB Output is correct
8 Correct 143 ms 64740 KB Output is correct
9 Correct 145 ms 64816 KB Output is correct
10 Correct 138 ms 64512 KB Output is correct
11 Correct 2401 ms 204656 KB Output is correct
12 Correct 2472 ms 204576 KB Output is correct
13 Correct 1394 ms 146572 KB Output is correct
14 Correct 1347 ms 146444 KB Output is correct
15 Correct 752 ms 113952 KB Output is correct
16 Correct 760 ms 114116 KB Output is correct
17 Correct 702 ms 113996 KB Output is correct
18 Correct 2396 ms 204864 KB Output is correct
19 Correct 31 ms 50224 KB Output is correct
20 Incorrect 31 ms 50252 KB Output isn't correct
21 Halted 0 ms 0 KB -