| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 208503 |
2020-03-11T11:05:55 Z |
srvlt |
Sails (IOI07_sails) |
C++14 |
|
529 ms |
7844 KB |
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define uint unsigned int
#define db long double
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(), (x).end()
void dout() { cerr << '\n'; }
template <typename Head, typename... Tail>
void dout(Head H, Tail... T) {
cerr << " " << H;
dout(T...);
}
#ifdef LOCAL
#define dbg(...) cerr << #__VA_ARGS__, dout(__VA_ARGS__)
#else
#define dbg(...) ;
#endif
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair <int, int> pii;
const int N = 100007;
int n, h[N], k[N], cnt[N];
struct node {
int l = 0, r = 0, lazy = 0;
ll s = 0;
void merge(const node & x, const node & y) {
s = x.s + y.s;
}
void upd() {
lazy = 1;
s = 0;
}
};
node t[(1 << 18) + 1];
void build(int v, int l, int r) {
t[v].l = l, t[v].r = r;
if (l == r) {
t[v].s = cnt[l];
return;
}
int m = l + r >> 1;
build(v << 1, l, m);
build(v << 1 | 1, m + 1, r);
t[v].merge(t[v << 1], t[v << 1 | 1]);
}
void push(int v) {
if (t[v].lazy) {
t[v << 1].upd();
t[v << 1 | 1].upd();
t[v].lazy = 0;
}
}
void update(int v, int l, int r) {
if (t[v].l > r || t[v].r < l) {
return;
}
if (t[v].l >= l && t[v].r <= r) {
t[v].upd();
return;
}
push(v);
update(v << 1, l, r);
update(v << 1 | 1, l, r);
t[v].merge(t[v << 1], t[v << 1 | 1]);
}
void change(int v, int pos, int x) {
if (t[v].l > pos || t[v].r < pos) {
return;
}
if (t[v].l == t[v].r) {
t[v].s = x;
return;
}
push(v);
int m = t[v].l + t[v].r >> 1;
if (pos <= m) {
change(v << 1, pos, x);
} else {
change(v << 1 | 1, pos, x);
}
t[v].merge(t[v << 1], t[v << 1 | 1]);
}
ll getsum(int v, int l, int r) {
if (t[v].l > r || t[v].r < l) {
return 0;
}
if (t[v].l >= l && t[v].r <= r) {
return t[v].s;
}
push(v);
return getsum(v << 1, l, r) + getsum(v << 1 | 1, l, r);
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(NULL);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
cin >> n;
int mx = 0;
for (int i = 1; i <= n; i++) {
cin >> h[i] >> k[i];
cnt[h[i] - k[i] + 1]++;
cnt[h[i] + 1]--;
mx = max(mx, h[i]);
}
for (int i = 1; i <= mx; i++) {
cnt[i] += cnt[i - 1];
}
build(1, 1, mx);
for (int i = 1; i < mx; i++) {
ll s = getsum(1, i + 1, mx), cur = getsum(1, i, i), nxt = getsum(1, i + 1, i + 1);
ll l = (nxt - cur + 1) / 2 - 1, r = (ll)1e10 + 1;
if (l < -1) {
l = -1;
}
while (l < r - 1) {
ll mid = (l + r) / 2;
if ((s - mid + (mx - i - 1)) / (mx - i) <= cur + mid) {
r = mid;
} else {
l = mid;
}
}
ll tmp = r;
change(1, i, cur + r);
l = i, r = mx + 1;
while (l < r - 1) {
ll mid = (l + r) / 2;
if (getsum(1, i + 1, mid) <= tmp) {
l = mid;
} else {
r = mid;
}
}
if (l >= i + 1) {
tmp -= getsum(1, i + 1, l);
update(1, i + 1, l);
}
if (l + 1 <= mx) {
change(1, l + 1, getsum(1, l + 1, l + 1) - tmp);
}
}
ll ans = 0;
for (int i = 1; i <= mx; i++) {
ll x = getsum(1, i, i);
ans += x * (x - 1) / 2;
}
cout << ans;
}
Compilation message
sails.cpp: In function 'void build(int, int, int)':
sails.cpp:57:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = l + r >> 1;
~~^~~
sails.cpp: In function 'void change(int, int, int)':
sails.cpp:94:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = t[v].l + t[v].r >> 1;
~~~~~~~^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
120 ms |
2172 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
108 ms |
2424 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
212 ms |
4216 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
529 ms |
7544 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
425 ms |
7672 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
472 ms |
7844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
