Submission #1308703

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308703		Minbaev	Palembang Bridges (APIO15_bridge)	C++20	0 / 100	2 ms	840 KiB

bridge

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimize("Ofast,unroll-loops")

using namespace std;
using namespace __gnu_pbds;

#define pb      push_back
#define all(x)  x.begin(),x.end()
#define int     long long
// #define double  long double
#define ar      array
#define mrand(a, b)   uniform_int_distribution<int>(a, b)(rng)

template<class T>bool umax(T &a,T b){if(a<=b){a=b;return true;}return false;}
template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;}

template<class T> using ste = tree<T, null_type, less_equal<T>,
rb_tree_tag, tree_order_statistics_node_update>;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int binpow(int a, int b, int m){
    if(b <= 0)return 1; 	
    if(b % 2 == 0){
        int c = binpow(a,b/2,m);
        return (c*c)%m;
    }
    return (binpow(a,b-1,m)*a)%m;
}

int divi(int a, int b, int m){
    return (a*(binpow(b,m-2, m)))%m;
}

namespace FAST {
    template<typename T>
    istream &operator>>(istream &cin, vector<T> &a) {
    for (T &i: a) cin >> i;
        return cin;
    }

    template<typename T>
    ostream &operator<<(ostream &cout, vector<T> &a) {
          for (T i: a) cout << i << ' ';
        return cout;
    }
}
using namespace FAST;

const int inf = 1e18 + 7;
const int mod = 1e9 + 7;
const int N = 1e2 + 5;
const int md = 998244353;

int rev(int a, int m){
	if (a == 1)return 1;
	return (1 - rev(m % a, a) * m) / a + m;
}

struct Bit {
    vector<int> b, b2;
    int n;

    Bit(int n) {
        this->n = n + 1;
        b.assign(n + 1, 0);
        b2.assign(n+1, 0);
    }

    void add(vector<int>&b, int idx, int x){
        while(idx <= n){
            b[idx] += x;
            idx += idx & -idx;
        }
    }

    void upd(int l, int r, int x){
        add(b, l, x);
        add(b, r+1, -x);
        add(b2, l, x*(l-1));
        add(b2, r+1, -x*r);
    }

    int sum(vector<int>&b, int idx){
        int res = 0;
        while(idx > 0){
            res += b[idx];
            idx -= idx & -idx;
        }
        return res;
    }

    int pref(int idx){
        return sum(b, idx) * idx - sum(b2, idx);
    }

    int get(int l, int r){                  
        return pref(r) - pref(l-1);
    }
};

int n,m,k;
int ans;

struct Tree{
	int sz;
	vector<vector<int>>t, pref;
	
	Tree(int n){
		this->sz = n;
		t.resize(sz * 4 + 5);
		pref.resize(sz * 4 + 5);
	}
	
	void merge(vector<int> &a, vector<int> &b, vector<int> &c, vector<int>&d){
		int i = 0, j = 0;
		while(i < a.size() && j < b.size()){
			if(a[i] <= b[j])c.pb(a[i++]);
			else c.pb(b[j++]);
		}
		while(i < a.size())c.pb(a[i++]);
		while(j < b.size())c.pb(b[j++]);
		
		d.pb(c[0]);
		for(int i = 1;i<c.size();i++){
			d.pb(d[i-1] + c[i]);
		}
	}
	
	void build(int tl, int tr, int v, vector<ar<int,2>> &op){
		if(tl == tr){
			t[v].pb(op[tl][1]);
			pref[v].pb(op[tl][1]);
			return;
		}
		int tm = (tl + tr) / 2;
		
		build(tl, tm, v*2, op);
		build(tm+1, tr, v*2+1, op);
		merge(t[v*2], t[v*2+1], t[v], pref[v]);
	}
	
	void get(int tl, int tr, int v, int l, int r, int val){
		if(r < tl || tr < l || r < l)return;
		if(l <= tl && tr <= r){
			int x = 0, y = t[v].size() - 1, ans2 = -1;
			while(x <= y){
				int mid = (x + y) / 2;
				
				if(t[v][mid] < val){
					ans2 = mid;
					x = mid + 1;
				}
				else y = mid - 1;
			}
			
			if(ans2 == -1)return;
			ans += val * (ans2 + 1) - pref[v][ans2];
			return;
		}
		int tm = (tl + tr) / 2;
		
		get(tl, tm, v*2, l, r, val);
		get(tm+1, tr, v*2+1, l, r, val);
	}
	
};

void solve(){
    
	cin >> k >> n;
	vector<ar<int,2>>vs;
	set<int>v_;
	vector<int>v;
	
	int sum = 0;
	for(int i = 1;i<=n;i++){
		char a,b;
		int l,r;
		cin >> a >> l >> b >> r;
		if(l > r)swap(l, r);
		if(a != b){
			vs.pb({l, r});
			v_.insert(l);
			v_.insert(r);
			sum += r-l + 1;
		}
		else sum += r-l;
	}
	
	for(auto to : v_){
		v.pb(to);
	}
	
	sort(all(vs));
	sort(all(v));
	
	int sz = vs.size();
	
	if(sz == 0){
		cout << sum << "\n";
		return;
	}
	
	vector<int>pref(sz + 5);
	pref[0] = vs[0][0];
	for(int i = 1;i<sz;i++){
		pref[i] = pref[i-1] + vs[i][0];
	}
	
	Tree t(sz + 5);
	t.build(0, sz, 1, vs);
	
	int l = 0, r = 1e9, ans3 = -1;
	while(l <= r){
		int l1 = l + (r-l)/3;
		int r1 = r - (r-l)/3;
		
		l1 = 4;
		
		int sum1 = 0, sum2 = 0;
		int pos1 = -1, pos2 = -1;
		int x = 0, y = sz - 1;
		while(x <= y){
			int mid = (x + y) / 2;
			
			if(vs[mid][0] < l1){
				x = mid + 1;
				pos1 = mid;
			}
			else y = mid - 1;
		}
		
		x = 0, y = sz - 1;
		while(x <= y){
			int mid = (x + y) / 2;
			
			if(vs[mid][0] < l1){
				x = mid + 1;
				pos2 = mid;
			}
			else y = mid - 1;
		}
		
		ans = 0;
		if(pos1 != -1)
			t.get(0, sz, 1, 0, pos1, l1);
		sum1 += pref[sz - 1] - ((pos1 == -1) ? 0 : pref[pos1]) - (sz-1 - pos1) * l1;
		sum1 += ans;
		
		ans = 0;
		if(pos2 != -1)
			t.get(0, sz, 1, 0, pos2, r1);
		sum2 += pref[sz - 1] - ((pos2 == -1) ? 0 : pref[pos2]) - (sz-1 - pos2) * r1;
		sum2 += ans;
		
		if(sum1 <= sum2){
			ans3 = sum1 * 2;
			r = r1 - 1;
		}
		else{
			ans3 = sum2 * 2;
			l = l1 + 1;
		}
		
		//~ cout << sum1 << "\n"; 
		
		//~ return;
	}
    
    cout << ans3 + sum << "\n";
    
}
/*
1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
//
5 6 1
1 1
-1 10
-1 10
-1 1000000000
-1 10
1 2 1
2 3 1
3 1 1
3 4 1
4 5 1
5 3 1
*/
 signed main()
{
  //~ freopen("road.in", "r", stdin);
  //~ freopen("road.out", "w", stdout);
    ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
    int tt=1;//cin >> tt;
    while(tt--)solve();    

}

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