Submission #641594

#	Time	Username	Problem	Language	Result	Execution time	Memory
641594		QwertyPi	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	245 ms	15248 KiB

bridge

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;

struct Person{
	int l, r;
};

int f(int x, Person p){
	if(x < p.l) return (p.l - x);
	if(x > p.r) return (x - p.r);
	return 0;
}

const int MAXN = 2e5 + 11;


int xs[MAXN], d[MAXN], k;

int ci(int x){
	return lower_bound(xs, xs + k, x) - xs;
}

struct BIT{
	int bit[MAXN + 3] = {0}, s = 0;
	void upd(int p, int v){
		p += 2;
		for(int i = p; i <= MAXN; i += i & -i){
			bit[i] += v;
		}
		s += v;
	}
	int qry(int p){
		int ret = 0;
		p += 2;
		for(int i = p; i; i -= i & -i){
			ret += bit[i];
		}
		return ret;
	}
	int bs(){
		int t = qry(MAXN);
		assert(t % 2 == 0);
		int idx = 0, val = 0;
		for(int j = 19; j >= 0; j--){
			if(idx + (1 << j) <= MAXN && val + bit[idx + (1 << j)] <= t / 2 - 1){
				val += bit[idx + (1 << j)]; idx += (1 << j);
			}
		}
		idx--;
		return idx;
	}
};

struct DS{
	BIT bit0, bit1; int rsum = 0;
	void upd(int p, int v, bool from_l){
		bit0.upd(p, v);
		bit1.upd(p, v * xs[p]);
		rsum += v * (from_l ? xs[p] : 0);
	}
	int qry(){
		int x = bit0.bs();
		int t = bit0.qry(MAXN) / 2;
		int c = bit0.qry(x - 1);
		int lsum = bit1.qry(x - 1) + xs[x] * (t - c);
		return rsum - lsum;
	}
} dsl, dsr;

int32_t main() {
	int K, n;
	cin >> K >> n;
	vector<Person> P;
	int C = 0;
	for(int i = 0; i < n; i++){
		char p, q; int s, t;
		cin >> p >> s >> q >> t;
		C += abs(s - t) + (p != q);
		if (p != q) {
			if(s > t) swap(s, t);
			P.push_back({s, t});
		}
	}

	vector<int> x;
	for(auto p : P) {
		x.push_back(p.l);
		x.push_back(p.r);
	}
	x.push_back(0);

	sort(x.begin(), x.end());
	x.resize(unique(x.begin(), x.end()) - x.begin());

	for(auto& i : x){
		i <<= 1;
	}
	for(auto& p : P){
		p.l <<= 1, p.r <<= 1;
	}

	for(int i = 0; i < x.size(); i++){
		xs[i] = x[i];
	}

	for(int i = 0; i + 1 < x.size(); i++){
		d[i] = xs[i + 1] - xs[i];
	}
	int ans = 1LL << 60;
	k = x.size();
	
	if (K == 1) {
		for(auto p : P){
			dsl.upd(ci(p.l), 1, 1);
			dsl.upd(ci(p.r), 1, 0);
		}
		cout << C + dsl.qry() << endl;
	} else {

		if(k == 0){
			cout << C << endl;
			return 0;
		}
		
		for(auto p : P){
			dsr.upd(ci(p.l), 1, 1);
			dsr.upd(ci(p.r), 1, 0);
		}
		
		sort(P.begin(), P.end(), [](Person a, Person b){
			return (a.l + a.r) / 2 < (b.l + b.r) / 2;
		});

		int ans = dsl.qry() + dsr.qry();
		for(int i = 0; i < P.size(); i++){
			dsl.upd(ci(P[i].l), 1, 1);
			dsl.upd(ci(P[i].r), 1, 0);
			dsr.upd(ci(P[i].l), -1, 1);
			dsr.upd(ci(P[i].r), -1, 0);
			ans = min(ans, dsl.qry() + dsr.qry());
		}
		
		cout << C + ans << endl;
	}
}

Compilation message (stderr)

bridge.cpp: In function 'int32_t main()':
bridge.cpp:105:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |  for(int i = 0; i < x.size(); i++){
      |                 ~~^~~~~~~~~~
bridge.cpp:109:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |  for(int i = 0; i + 1 < x.size(); i++){
      |                 ~~~~~~^~~~~~~~~~
bridge.cpp:138:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Person>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |   for(int i = 0; i < P.size(); i++){
      |                  ~~^~~~~~~~~~
bridge.cpp:112:6: warning: unused variable 'ans' [-Wunused-variable]
  112 |  int ans = 1LL << 60;
      |      ^~~

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 32 / 32
• Subtask 5: 37 / 37