oj.uz

Submission #446114

# Submission time Handle Problem Language Result Execution time Memory
446114 2021-07-21T01:02:28 Z kig9981 Treatment Project (JOI20_treatment) C++17
9 / 100
 560 ms 55484 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;
vector<pair<int,int>> tree[2*SZ];
vector<pair<int,long long>> U[200000], qry[200000];
vector<int> P, x, y;
vector<tuple<int,int,int,int,int>> A;
long long dist1[100000], dist2[100000], mtree[200001];
int chk[100000];

void set_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_back(p,i);
		if(~e&1) tree[e--].emplace_back(p,i);
	}
}

void get_pos(int n, int l)
{
	for(n+=SZ;n;n>>=1) while(tree[n].size() && l<=tree[n].back().first) {
		P.push_back(tree[n].back().second);
		tree[n].pop_back();
	}
}

void update(int n, long long v) {for(++n;n<=200000;n+=n&-n) mtree[n]=min(mtree[n],v);}

long long get_min(int n)
{
	long long ret=INF;
	for(++n;n;n-=n&-n) ret=min(ret,mtree[n]);
	return ret;
}

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=INF;
	cin>>N>>M; A.resize(M);
	memset(dist1,0x3f,sizeof(dist1));
	memset(dist2,0x3f,sizeof(dist2));
	for(int i=0;i<M;i++) {
		auto &[t,l,r,aa,c]=A[i];
		cin>>t>>l>>r>>c;
		if(--l==0) chk[i]|=1;
		if(r==N) chk[i]|=2;
		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(-(dist1[i]=c),i);
		else set_tree(x1,x2,-y1,i);
	}
	for(int i=2*SZ;--i;) sort(tree[i].begin(),tree[i].end());
	while(!Q.empty()) {
		auto[t,c]=Q.top();
		Q.pop();
		P.clear();
		auto[x1,y1,x2,y2,d]=A[c];
		get_pos(x2,-y2);
		for(auto n: P) if(dist1[n]==INF) {
			auto[x1,y1,x2,y2,d]=A[n];
			dist1[n]=dist1[c]+d;
			Q.emplace(-dist1[n],n);
		}
	}
	for(int i=2*SZ;--i;) tree[i].clear();
	for(int i=0;i<M;i++) {
		auto[x1,y1,x2,y2,c]=A[i];
		if(chk[i]&2) Q.emplace(-(dist2[i]=c),i);
		else set_tree(y1,y2,x2,i);
	}
	for(int i=2*SZ;--i;) sort(tree[i].begin(),tree[i].end());
	while(!Q.empty()) {
		auto[t,c]=Q.top();
		Q.pop();
		P.clear();
		auto[x1,y1,x2,y2,d]=A[c];
		get_pos(y1,x1);
		for(auto n: P) if(dist2[n]==INF) {
			auto[x1,y1,x2,y2,d]=A[n];
			dist2[n]=dist2[c]+d;
			Q.emplace(-dist2[n],n);
		}
	}
	for(int i=0;i<M;i++) {
		auto[x1,y1,x2,y2,c]=A[i];
		ans=min(ans,dist1[i]+dist2[i]-c);
		U[x1].emplace_back(y1,dist2[i]);
		qry[x2].emplace_back(y2,dist1[i]);
	}
	memset(mtree,0x3f,sizeof(mtree));
	for(int i=0;i<x.size();i++) {
		for(auto[p,v]: U[i]) update(p,v);
		for(auto[p,v]: qry[i]) ans=min(ans,get_min(p)+v);
	}
	cout<<(ans<INF ? ans:-1)<<'\n';
	return 0;
}

Compilation message

treatment.cpp: In function 'int main()':
treatment.cpp:121:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |  for(int i=0;i<x.size();i++) {
      |              ~^~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 39652 KB Output is correct
2 Correct 222 ms 39568 KB Output is correct
3 Correct 341 ms 45996 KB Output is correct
4 Correct 356 ms 46404 KB Output is correct
5 Correct 150 ms 35020 KB Output is correct
6 Correct 148 ms 34752 KB Output is correct
7 Correct 144 ms 36272 KB Output is correct
8 Correct 102 ms 33140 KB Output is correct
9 Correct 111 ms 34172 KB Output is correct
10 Correct 125 ms 35500 KB Output is correct
11 Correct 523 ms 55484 KB Output is correct
12 Correct 507 ms 53676 KB Output is correct
13 Correct 560 ms 51184 KB Output is correct
14 Correct 538 ms 51288 KB Output is correct
15 Correct 431 ms 46384 KB Output is correct
16 Correct 443 ms 46892 KB Output is correct
17 Correct 430 ms 46460 KB Output is correct
18 Correct 516 ms 54312 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 25036 KB Output is correct
2 Correct 17 ms 25064 KB Output is correct
3 Correct 17 ms 25132 KB Output is correct
4 Correct 17 ms 25128 KB Output is correct
5 Correct 18 ms 25124 KB Output is correct
6 Correct 17 ms 25116 KB Output is correct
7 Correct 17 ms 25136 KB Output is correct
8 Correct 19 ms 25036 KB Output is correct
9 Correct 17 ms 25164 KB Output is correct
10 Correct 18 ms 25080 KB Output is correct
11 Correct 17 ms 25032 KB Output is correct
12 Correct 17 ms 25148 KB Output is correct
13 Correct 17 ms 25036 KB Output is correct
14 Correct 17 ms 25076 KB Output is correct
15 Correct 17 ms 25028 KB Output is correct
16 Correct 18 ms 25128 KB Output is correct
17 Correct 17 ms 25036 KB Output is correct
18 Correct 17 ms 25152 KB Output is correct
19 Correct 17 ms 25160 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 25036 KB Output is correct
2 Correct 17 ms 25064 KB Output is correct
3 Correct 17 ms 25132 KB Output is correct
4 Correct 17 ms 25128 KB Output is correct
5 Correct 18 ms 25124 KB Output is correct
6 Correct 17 ms 25116 KB Output is correct
7 Correct 17 ms 25136 KB Output is correct
8 Correct 19 ms 25036 KB Output is correct
9 Correct 17 ms 25164 KB Output is correct
10 Correct 18 ms 25080 KB Output is correct
11 Correct 17 ms 25032 KB Output is correct
12 Correct 17 ms 25148 KB Output is correct
13 Correct 17 ms 25036 KB Output is correct
14 Correct 17 ms 25076 KB Output is correct
15 Correct 17 ms 25028 KB Output is correct
16 Correct 18 ms 25128 KB Output is correct
17 Correct 17 ms 25036 KB Output is correct
18 Correct 17 ms 25152 KB Output is correct
19 Correct 17 ms 25160 KB Output is correct
20 Correct 31 ms 26440 KB Output is correct
21 Correct 30 ms 26488 KB Output is correct
22 Incorrect 27 ms 26096 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 39652 KB Output is correct
2 Correct 222 ms 39568 KB Output is correct
3 Correct 341 ms 45996 KB Output is correct
4 Correct 356 ms 46404 KB Output is correct
5 Correct 150 ms 35020 KB Output is correct
6 Correct 148 ms 34752 KB Output is correct
7 Correct 144 ms 36272 KB Output is correct
8 Correct 102 ms 33140 KB Output is correct
9 Correct 111 ms 34172 KB Output is correct
10 Correct 125 ms 35500 KB Output is correct
11 Correct 523 ms 55484 KB Output is correct
12 Correct 507 ms 53676 KB Output is correct
13 Correct 560 ms 51184 KB Output is correct
14 Correct 538 ms 51288 KB Output is correct
15 Correct 431 ms 46384 KB Output is correct
16 Correct 443 ms 46892 KB Output is correct
17 Correct 430 ms 46460 KB Output is correct
18 Correct 516 ms 54312 KB Output is correct
19 Correct 17 ms 25036 KB Output is correct
20 Correct 17 ms 25064 KB Output is correct
21 Correct 17 ms 25132 KB Output is correct
22 Correct 17 ms 25128 KB Output is correct
23 Correct 18 ms 25124 KB Output is correct
24 Correct 17 ms 25116 KB Output is correct
25 Correct 17 ms 25136 KB Output is correct
26 Correct 19 ms 25036 KB Output is correct
27 Correct 17 ms 25164 KB Output is correct
28 Correct 18 ms 25080 KB Output is correct
29 Correct 17 ms 25032 KB Output is correct
30 Correct 17 ms 25148 KB Output is correct
31 Correct 17 ms 25036 KB Output is correct
32 Correct 17 ms 25076 KB Output is correct
33 Correct 17 ms 25028 KB Output is correct
34 Correct 18 ms 25128 KB Output is correct
35 Correct 17 ms 25036 KB Output is correct
36 Correct 17 ms 25152 KB Output is correct
37 Correct 17 ms 25160 KB Output is correct
38 Correct 31 ms 26440 KB Output is correct
39 Correct 30 ms 26488 KB Output is correct
40 Incorrect 27 ms 26096 KB Output isn't correct
41 Halted 0 ms 0 KB -