oj.uz

Submission #563515

# Submission time Handle Problem Language Result Execution time Memory
563515 2022-05-17T11:35:19 Z ACE_ Palembang Bridges (APIO15_bridge) C++14
100 / 100
 495 ms 36320 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define f first
#define s second
#define endl "\n"
const int N = 2e5 + 5;
int t[4*N],idx,sm[4*N],s[N],p[N],pos[N];
map<int,int>id;
void compress(vector<pii>v){
	idx=0;
	sort(v.begin(),v.end());
	for(int i=0;i<v.size();i++){
		++idx;
		id[v[i].s]=idx;pos[idx]=v[i].f;
	}
}
void upd(int u,int id,int l,int r){
	if(l==r){
		t[u]++;
		sm[u]+=pos[l];
		return;
	}
	int mid=(l+r)/2;
	if(id<=mid)upd(2*u,id,l,mid);
	else upd(2*u+1,id,mid+1,r);
	t[u]=t[2*u+1]+t[2*u];
	sm[u]=sm[2*u+1]+sm[2*u];
}
int get(int u,int id,int l,int r){
	if(l==r)return l;
	int mid=(l+r)/2;
	if(t[2*u]>=id)return get(2*u,id,l,mid);
	return get(2*u+1,id-t[2*u],mid+1,r);
}
int sum(int u,int st,int en,int l,int r){
	if(l>en||r<st)return 0;
	if(st<=l&&r<=en)return sm[u];
	int mid=(l+r)/2;
	return sum(2*u,st,en,l,mid)+sum(2*u+1,st,en,mid+1,r);
}
main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int k,n;
	cin>>k>>n;
	vector<pair<int,pii> > x;
	vector<pii>v;
	int X=0;
	for(int i=1;i<=n;i++){
		char c,cc;
		int a,b;
		cin>>c>>a>>cc>>b;
		if(c==cc)X+=abs(b-a);
		else{
			idx+=2;
			x.push_back({a+b,{idx-1,idx}});
			v.push_back({a,idx-1});v.push_back({b,idx});
		}
	}
	idx=0;
	compress(v);
	sort(x.begin(),x.end());
	for(int i=0;i<x.size();i++){
		upd(1,id[x[i].s.f],1,idx);
		upd(1,id[x[i].s.s],1,idx);
		int mid=get(1,(i+1),1,idx);
		p[i]=-sum(1,1,mid,1,idx)+sum(1,mid+1,idx,1,idx);
	}
	int ans=p[x.size()-1];
	if(k==1)cout<<p[x.size()-1]+X+(int)x.size();
	else{
		for(int u = 1; u <= 4*idx;u++) t[u]=sm[u]=0;
		int c = 0;
		for(int i=(int)x.size()-1;i>=0;i--){
			upd(1,id[x[i].s.f],1,idx);
			upd(1,id[x[i].s.s],1,idx); ++c;
			int mid=get(1,c,1,idx);
		
			s[i]=-sum(1,1,mid,1,idx)+sum(1,mid+1,idx,1,idx);
			if(i>0)ans=min(ans,s[i]+p[i-1]);
		}	
		cout<<ans+X+(int)x.size();	
	}
}

Compilation message

bridge.cpp: In function 'void compress(std::vector<std::pair<long long int, long long int> >)':
bridge.cpp:14:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |  for(int i=0;i<v.size();i++){
      |              ~^~~~~~~~~
bridge.cpp: At global scope:
bridge.cpp:43:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   43 | main(){
      | ^~~~
bridge.cpp: In function 'int main()':
bridge.cpp:64:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |  for(int i=0;i<x.size();i++){
      |              ~^~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 2 ms 596 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 158 ms 28864 KB Output is correct
13 Correct 319 ms 29136 KB Output is correct
14 Correct 271 ms 26824 KB Output is correct
15 Correct 163 ms 16372 KB Output is correct
16 Correct 153 ms 28916 KB Output is correct
17 Correct 139 ms 28844 KB Output is correct
18 Correct 153 ms 28896 KB Output is correct
19 Correct 221 ms 28860 KB Output is correct
20 Correct 166 ms 28900 KB Output is correct
21 Correct 149 ms 28868 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 328 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 224 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 328 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 2 ms 724 KB Output is correct
14 Correct 3 ms 724 KB Output is correct
15 Correct 3 ms 724 KB Output is correct
16 Correct 1 ms 456 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 2 ms 724 KB Output is correct
20 Correct 2 ms 724 KB Output is correct
21 Correct 2 ms 724 KB Output is correct
22 Correct 2 ms 660 KB Output is correct
23 Correct 2 ms 720 KB Output is correct
24 Correct 3 ms 724 KB Output is correct

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 2 ms 724 KB Output is correct
14 Correct 2 ms 724 KB Output is correct
15 Correct 3 ms 724 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 2 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 2 ms 656 KB Output is correct
20 Correct 2 ms 652 KB Output is correct
21 Correct 2 ms 724 KB Output is correct
22 Correct 3 ms 644 KB Output is correct
23 Correct 2 ms 720 KB Output is correct
24 Correct 2 ms 652 KB Output is correct
25 Correct 249 ms 34744 KB Output is correct
26 Correct 410 ms 34996 KB Output is correct
27 Correct 495 ms 35640 KB Output is correct
28 Correct 482 ms 36320 KB Output is correct
29 Correct 483 ms 36280 KB Output is correct
30 Correct 209 ms 19436 KB Output is correct
31 Correct 207 ms 35572 KB Output is correct
32 Correct 215 ms 36204 KB Output is correct
33 Correct 208 ms 35848 KB Output is correct
34 Correct 337 ms 36244 KB Output is correct
35 Correct 246 ms 35824 KB Output is correct
36 Correct 233 ms 36052 KB Output is correct
37 Correct 233 ms 34748 KB Output is correct