oj.uz

Submission #391797

# Submission time Handle Problem Language Result Execution time Memory
391797 2021-04-19T21:21:56 Z osaaateiasavtnl Palembang Bridges (APIO15_bridge) C++14
100 / 100
 252 ms 15524 KB 
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <fstream>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define x first
#define y second
#define Time (double)clock()/CLOCKS_PER_SEC
#define debug(x) std::cerr << #x << ": " << x << '\n';
#define FOR(i, n) for (int i = 0; i < n; ++i)
#define FORN(i, n) for (int i = 1; i <= n; ++i)
#define pb push_back
#define trav(a, x) for (auto& a : x)
using vi = vector<int>;
template <typename T>
std::istream& operator >>(std::istream& input, std::vector<T>& data)
{
    for (T& x : data)
        input >> x;
    return input;
}
template <typename T>
std::ostream& operator <<(std::ostream& output, const pair <T, T> & data)
{
    output << "(" << data.x << "," << data.y << ")";
    return output;
}
template <typename T>
std::ostream& operator <<(std::ostream& output, const std::vector<T>& data)
{
    for (const T& x : data)
        output << x << " ";
    return output;
}
ll div_up(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
ll div_down(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down 
ll math_mod(ll a, ll b) { return a - b * div_down(a, b); }
#define tcT template<class T
#define tcTU tcT, class U
tcT> using V = vector<T>; 
tcT> void re(V<T>& x) { 
    trav(a, x)
        cin >> a;
}
tcT> bool ckmin(T& a, const T& b) {
    return b < a ? a = b, 1 : 0; 
} // set a = min(a,b)
tcT> bool ckmax(T& a, const T& b) {
    return a < b ? a = b, 1 : 0; 
}
ll gcd(ll a, ll b) {
    while (b) {
        tie(a, b) = mp(b, a % b);
    }
    return a;
}

const int LG = 18, N = 1 << LG;
int f[1 << LG];

void clear() {
	memset(f, 0, sizeof f);
}
void add(int i) {
	for (; i < N; i |= i + 1) {
		f[i]++;
	}
}
int get(int k) {
	int i = 0;
	for (int bit = LG - 1; bit >= 0; --bit) {
		int b = f[i + (1 << bit) - 1];
		if (b < k) {
			k -= b;
			i += 1 << bit;
		}
	}
	return i;
}

struct Fen {

int f[N];
void clear() {
	memset(f, 0, sizeof f);
}
void add(int i, int x) {
	for (; i < N; i |= i + 1) {
		f[i] += x;
	}
}
int get(int i) {
	int ans = 0;
	for (; i >= 0; i &= i + 1, --i) {
		ans += f[i];
	}
	return ans;
}
int get(int l, int r) {
	return get(r) - get(l - 1);
}

};

vi co;

struct Dist {

Fen cnt, sum;
void clear() {
	cnt.clear();
	sum.clear();
}
void add(int i) {
	cnt.add(i, 1);
	sum.add(i, co[i]);
}
int left(int i) {
	return co[i] * cnt.get(i) - sum.get(i);
}
int right(int i) {
	return sum.get(i, N - 1) - co[i] * cnt.get(i, N - 1);
}

} L, R;	

int pref[N], suf[N];

signed main() {
    #ifdef LOCAL
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif

    int k, n;
    cin >> k >> n;
    int AD = 0;
    V <ii> a;

    FOR (i, n) {
    	char t1, t2;
    	int l, r;
    	cin >> t1 >> l >> t2 >> r;
    	if (r < l) {
    		swap(l, r);
    	}
    	AD += r - l;
    	if (t1 != t2) {
    		a.app(mp(l, r));
    		co.app(l);
    		co.app(r);
    		AD++;
    	}
    }

    auto comp = [&] (ii a, ii b) {
    	return a.x + a.y < b.x + b.y;
    };
    sort(all(a), comp);
    sort(all(co));

   	if (k == 2) {
	    auto Pos = [&] (int x) {
	    	return lower_bound(all(co), x) - co.begin();
	    };

	    int sz = a.size();

	    FOR (l, sz) {
	    	add(Pos(a[l].x));
	    	add(Pos(a[l].y));
	    	L.add(Pos(a[l].x));
	    	R.add(Pos(a[l].y));
	    	int x = get(l + 1);
	    	pref[l + 1] = R.left(x) + L.right(x);
	    }
	    clear();
	    L.clear();
	    R.clear();
	    for (int r = sz - 1; r >= 0; --r) {
	    	add(Pos(a[r].x));
	    	add(Pos(a[r].y));
	    	L.add(Pos(a[r].x));
	    	R.add(Pos(a[r].y));
	    	int x = get(sz - r);
	    	suf[r] = R.left(x) + L.right(x);
	    }

	    int ans = 1e18;
	    FOR (i, sz + 1) {
	    	ckmin(ans, pref[i] + suf[i]);
	    }

	    cout << 2 * ans + AD << endl;   		
   	}
   	else {

   		vi c;
   		trav (e, a) {
   			c.app(e.x);
   			c.app(e.y);
   		}
   		sort(all(c));

	    int sz = a.size();
	 
	    int ans = 0;
	    if (sz) {
	    	int X = c[sz - 1];
		    trav (e, a) {
		    	if (e.x > X) {
		    		ans += e.x - X;
		    	}
		    	else if (e.y < X) {
		    		ans += X - e.y;
		    	}
		    }    	
	    }
	 
		cout << ans * 2 + AD << endl;
   	}

}

Subtask #1
8.0 / 8.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 33 ms 6568 KB Output is correct
13 Correct 74 ms 6540 KB Output is correct
14 Correct 57 ms 6124 KB Output is correct
15 Correct 42 ms 3696 KB Output is correct
16 Correct 37 ms 6524 KB Output is correct
17 Correct 44 ms 6448 KB Output is correct
18 Correct 51 ms 6512 KB Output is correct
19 Correct 71 ms 6440 KB Output is correct
20 Correct 42 ms 6436 KB Output is correct
21 Correct 57 ms 6432 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10548 KB Output is correct
2 Correct 5 ms 10572 KB Output is correct
3 Correct 6 ms 10484 KB Output is correct
4 Correct 6 ms 10572 KB Output is correct
5 Correct 6 ms 10476 KB Output is correct
6 Correct 6 ms 10504 KB Output is correct
7 Correct 5 ms 10572 KB Output is correct
8 Correct 6 ms 10572 KB Output is correct
9 Correct 5 ms 10572 KB Output is correct
10 Correct 5 ms 10572 KB Output is correct
11 Correct 5 ms 10572 KB Output is correct
12 Correct 5 ms 10532 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10572 KB Output is correct
2 Correct 5 ms 10524 KB Output is correct
3 Correct 5 ms 10572 KB Output is correct
4 Correct 5 ms 10572 KB Output is correct
5 Correct 5 ms 10572 KB Output is correct
6 Correct 5 ms 10572 KB Output is correct
7 Correct 5 ms 10480 KB Output is correct
8 Correct 5 ms 10572 KB Output is correct
9 Correct 5 ms 10584 KB Output is correct
10 Correct 6 ms 10572 KB Output is correct
11 Correct 6 ms 10572 KB Output is correct
12 Correct 5 ms 10572 KB Output is correct
13 Correct 6 ms 10572 KB Output is correct
14 Correct 7 ms 10572 KB Output is correct
15 Correct 7 ms 10572 KB Output is correct
16 Correct 6 ms 10572 KB Output is correct
17 Correct 6 ms 10572 KB Output is correct
18 Correct 7 ms 10572 KB Output is correct
19 Correct 6 ms 10648 KB Output is correct
20 Correct 7 ms 10572 KB Output is correct
21 Correct 7 ms 10572 KB Output is correct
22 Correct 7 ms 10572 KB Output is correct
23 Correct 6 ms 10572 KB Output is correct
24 Correct 7 ms 10572 KB Output is correct

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10572 KB Output is correct
2 Correct 5 ms 10572 KB Output is correct
3 Correct 5 ms 10572 KB Output is correct
4 Correct 7 ms 10572 KB Output is correct
5 Correct 6 ms 10592 KB Output is correct
6 Correct 5 ms 10572 KB Output is correct
7 Correct 5 ms 10572 KB Output is correct
8 Correct 5 ms 10572 KB Output is correct
9 Correct 5 ms 10572 KB Output is correct
10 Correct 5 ms 10572 KB Output is correct
11 Correct 5 ms 10572 KB Output is correct
12 Correct 6 ms 10572 KB Output is correct
13 Correct 6 ms 10572 KB Output is correct
14 Correct 7 ms 10572 KB Output is correct
15 Correct 7 ms 10572 KB Output is correct
16 Correct 5 ms 10572 KB Output is correct
17 Correct 6 ms 10572 KB Output is correct
18 Correct 6 ms 10576 KB Output is correct
19 Correct 6 ms 10628 KB Output is correct
20 Correct 7 ms 10628 KB Output is correct
21 Correct 6 ms 10668 KB Output is correct
22 Correct 7 ms 10572 KB Output is correct
23 Correct 6 ms 10572 KB Output is correct
24 Correct 7 ms 10572 KB Output is correct
25 Correct 112 ms 15428 KB Output is correct
26 Correct 132 ms 15400 KB Output is correct
27 Correct 229 ms 15448 KB Output is correct
28 Correct 252 ms 15384 KB Output is correct
29 Correct 244 ms 15524 KB Output is correct
30 Correct 115 ms 13228 KB Output is correct
31 Correct 110 ms 15420 KB Output is correct
32 Correct 146 ms 15388 KB Output is correct
33 Correct 136 ms 15500 KB Output is correct
34 Correct 164 ms 15408 KB Output is correct
35 Correct 112 ms 15464 KB Output is correct
36 Correct 159 ms 15520 KB Output is correct
37 Correct 123 ms 15440 KB Output is correct