| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 683803 |
2023-01-19T11:30:27 Z |
ghostwriter |
Sails (IOI07_sails) |
C++17 |
|
51 ms |
2636 KB |
#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define bg begin
#define ed end
#define ft front
#define bk back
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define ins insert
#define ers erase
#define all(x) (x).bg(), (x).ed()
#define sz(x) (int)(x).size()
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pi pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vll vector<ll>
#define vpi vector<pi>
#define vpll vector<pll>
#define str string
#define FOR(i, l, r) for (int i = (l); i <= (r); ++i)
#define FOS(i, r, l) for (int i = (r); i >= (l); --i)
#define FRN(i, n) for (int i = 0; i < (n); ++i)
#define FSN(i, n) for (int i = (n) - 1; i >= 0; --i)
#define EACH(i, x) for (auto &i : x)
#define WHILE while
template<typename T> T gcd(T a, T b) { WHILE(b) { a %= b; swap(a, b); } return a; }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
/*
Pretty hard greedy problem :v. Rearrange all pair (h, k) in increasing order. Iterate from 1 to n and in each position, choose
all the smallest value an increase it by 1 (also increase the answer as well). We can proof this with greedy exchange (a lot of greedy exchange) and induction
but the intuition is to reduce the imbalance between heights.
*/
const int N = 1e5 + 1;
int n;
pi a[N];
pll f[N];
pll operator +(const pll &a, const pll &b) { return {a.st + b.st, a.nd + b.nd}; }
void operator +=(pll &a, const pll &b) { a = a + b; }
void upd(int pos, int v) { for (int i = pos; i < N; i += (i & -i)) { f[i].st += v; f[i].nd += 1LL * pos * v; } }
void upd(int l, int r, int v) { upd(l, v); upd(r + 1, -v); }
ll get(int pos) { pll rs = {0, 0}; for (int i = pos; i > 0; i -= (i & -i)) rs += f[i]; return (pos + 1) * rs.st - rs.nd; }
ll get(int l, int r) { return get(r) - get(l - 1); }
int get1(int pos) { int rs = 0; for (int i = pos; i > 0; i -= (i & -i)) rs += f[i].st; return rs; }
pi getp(int x) {
pi rs = {N, 0}, cur = {0, 0}, sum = {0, 0};
FSN(i, 17) {
if (cur.st + (1 << i) < N) {
int tmp = cur.st + (1 << i);
if (sum.st + f[tmp].st == x) rs.st = min(rs.st, tmp);
else if (sum.st + f[tmp].st > x) {
cur.st = tmp;
sum.st += f[tmp].st;
}
}
if (cur.nd + (1 << i) < N) {
int tmp = cur.nd + (1 << i);
if (sum.nd + f[tmp].st == x) {
rs.nd = max(rs.nd, tmp);
cur.nd = tmp;
sum.nd += f[tmp].st;
}
else if (sum.nd + f[tmp].st > x) {
cur.nd = tmp;
sum.nd += f[tmp].st;
}
}
}
return rs;
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen(file".inp", "r", stdin);
// freopen(file".out", "w", stdout);
cin >> n;
FOR(i, 1, n) cin >> a[i].st >> a[i].nd;
sort(a + 1, a + 1 + n);
ll rs = 0;
FOR(i, 1, n) {
rs += get(a[i].st - a[i].nd + 1, a[i].st);
int maxv = get1(a[i].st - a[i].nd + 1);
pi pos = getp(maxv);
pos.nd = min(pos.nd, a[i].st);
// cerr << a[i].st << ' ' << a[i].nd << " ; " << pos.st << ' ' << pos.nd << '\n';
if (pos.nd + 1 <= a[i].st) upd(pos.nd + 1, a[i].st, 1);
int rm = a[i].nd - a[i].st + pos.nd;
if (rm) upd(pos.st, pos.st + rm - 1, 1);
// cerr << a[i].st << " - " << a[i].nd << " : " << maxv << '\n';
// cerr << i << " : \n";
// cerr << pos.st << ' ' << pos.nd << '\n';
// cerr << rm << '\n';
// cerr << pos.nd + 1 << ' ' << a[i].st << '\n';
// cerr << pos.st << ' ' << pos.st + rm - 1 << '\n';
// cerr << '\n';
}
cout << rs;
return 0;
}
/*
4
3 3
9 1
9 5
3 2
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1876 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
852 KB |
Output is correct |
| 2 |
Correct |
15 ms |
640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
940 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
1492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
49 ms |
2388 KB |
Output is correct |
| 2 |
Correct |
41 ms |
2468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
2472 KB |
Output is correct |
| 2 |
Correct |
31 ms |
2388 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
51 ms |
2636 KB |
Output is correct |
| 2 |
Correct |
35 ms |
1488 KB |
Output is correct |
