oj.uz

답안 #1105805

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1105805 2024-10-27T22:49:11 Z _rain_ Palembang Bridges (APIO15_bridge) C++14
0 / 100
 1 ms 592 KB 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define name "main"
#define int long long
typedef pair<int,int> ii;
#define fi first 
#define se second

const int N=(int)1e5;
bool print=false;
vector<ii>sett;
vector<ll>nen;
int n,k,cnt=0;
ll f[N+2];
bool used[N*2+2];

bool cmp(ii a,ii b){
	return a.fi+a.se<b.fi+b.se;
}
class BIT{
public:
	vector<ll>tot;
	vector<int> cnt,one;
	int n;
	void init(int _n){
		n=_n;
		tot.assign(_n+2,0);
		cnt.assign(_n+2,0);
		one.assign(_n+2,0);
		return;
	}
	void upd_tot(int id,int val){
		for(;id<=n;id+=(id&(-id)))
			tot[id]+=val;
		return;
	}
	void upd_cnt(int id,int val){
		for(;id<=n;id+=(id&(-id)))
			cnt[id]+=val;
		return;
	}
	void upd_one(int id,int val){
		for(;id<=n;id+=(id&(-id)))
			one[id]+=val;
	}
	int Get_tot(int id){
		ll sum=0;
		for(;id;id-=(id&(-id)))
			sum+=tot[id];
		return sum;
	}
	ll Get_cnt(int id){
		ll sum=0;
		for(;id;id-=(id&(-id)))
			sum+=cnt[id];

		return sum;
	}
	ll Get_one(int id){
		ll sum=0;
		for(;id;id-=(id&(-id)))
			sum+=one[id];
		return sum;
	}
	ll sum_range(int t,int l,int r){
		if (t==1){
			return Get_tot(r)-Get_tot(l-1);
		}
		if (t==2){
			return Get_cnt(r)-Get_cnt(l-1);
		}
		if (t==3){
			return Get_one(r)-Get_one(l-1);	
		}
	}
};	
BIT tree;

ll F(int i){
	int l=1,r=nen.size(),p=1;
	while(l<=r){
		int m=(l+r)>>1;
		if (tree.sum_range(3,1,m)<=(cnt+1)/2){
			l=m+1,p=m;
		}
		else r=m-1;
	}
	return nen[p]*tree.sum_range(2,1,p)-tree.sum_range(1,1,p)+tree.sum_range(1,p+1,nen.size())-nen[p]*tree.sum_range(2,p+1,nen.size())+(ll)i;
}

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	// freopen(name".inp","r",stdin);
	// freopen(name".out","w",stdout);
	cin>>k>>n;
	ll ans=0;
	nen.push_back(-1);
	for (int i=1;i<=n;++i){
		char c1,c2; int a,b;
		cin>>c1>>a>>c2>>b;
		if (c1==c2) ans+=abs(a-b);
		else {
			nen.push_back(a);
			nen.push_back(b);
			sett.push_back({a,b});
		}
	}
	sort(nen.begin(),nen.end()); nen.resize(unique(nen.begin(),nen.end())-nen.begin());
	sort(sett.begin(),sett.end(),cmp);
	tree.init(nen.size());
	for (int i=1;i<=sett.size();++i){
		int a=sett[i-1].fi,b=sett[i-1].se;
		a=upper_bound(nen.begin(),nen.end(),a)-nen.begin();
		b=upper_bound(nen.begin(),nen.end(),b)-nen.begin();
		tree.upd_cnt(a,1),tree.upd_cnt(b,1);
		tree.upd_tot(a,nen[a-1]),tree.upd_tot(b,nen[b-1]);
		if (!used[a]) used[a]=true,tree.upd_one(a,1),++cnt;
		if (!used[b]) used[b]=true,tree.upd_one(b,1),++cnt;
		f[i]=F(i);
	}
	if (k==1) ans=ans+f[sett.size()];
	cout<<ans;
	exit(0);
}

Compilation message

bridge.cpp: In function 'int32_t main()':
bridge.cpp:114:16: 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]
  114 |  for (int i=1;i<=sett.size();++i){
      |               ~^~~~~~~~~~~~~
bridge.cpp: In member function 'll BIT::sum_range(long long int, long long int, long long int)':
bridge.cpp:77:2: warning: control reaches end of non-void function [-Wreturn-type]
   77 |  }
      |  ^

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 552 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 480 KB Output is correct
8 Correct 1 ms 504 KB Output is correct
9 Incorrect 1 ms 592 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 504 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Incorrect 1 ms 504 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Incorrect 1 ms 336 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Incorrect 1 ms 336 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Incorrect 1 ms 336 KB Output isn't correct
4 Halted 0 ms 0 KB -