| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 528854 |
2022-02-21T15:24:21 Z |
cig32 |
Sails (IOI07_sails) |
C++17 |
|
224 ms |
15412 KB |
#include "bits/stdc++.h"
using namespace std;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
const int MAXN = 1e5 + 10;
const int MOD = 1e9 + 7;
#define int long long
int rnd(int x, int y) {
int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
struct mast {
int height;
int cnt;
};
bool cmp(mast a, mast b) {
if(a.height == b.height) return a.cnt < b.cnt;
return a.height < b.height;
}
struct segtree_dec {
// #define int long long required!!!
// Maintain a monotonically decreasing(!!!) array, initially all zeros
// Maintain the following two types of queries:
// 1. Given i, find range of indices [l, r] s.t. a[i] = a[j] for all l ≤ j ≤ r (parallel binary search, log(n))
// 2. Given l, r, v, perform a[i] += v for all l ≤ i ≤ r
// 3. Given l, r, compute a[l] + a[l+1] + ... + a[r]
// 4. Given l, r, compute max(a[l], a[l+1], ..., a[r]) ( = a[l])
// 5. Given l, r, compute min(a[l], a[l+1], ..., a[r]) ( = a[r])
struct node {
int mi = 0, ma = 0, upd = 0, sum = 0;
};
vector<node> a;
int stok;
void u(int l, int r, int constl, int constr, int idx, int v) {
if(l<=constl && constr<=r) {
a[idx].mi += v;
a[idx].ma += v;
a[idx].upd += v;
a[idx].sum += v * (constr-constl+1);
return;
}
int mid = (constl + constr) >> 1;
if(a[idx].upd != 0) {
a[2*idx+1].mi += a[idx].upd;
a[2*idx+2].mi += a[idx].upd;
a[2*idx+1].ma += a[idx].upd;
a[2*idx+2].ma += a[idx].upd;
a[2*idx+1].upd += a[idx].upd;
a[2*idx+2].upd += a[idx].upd;
a[2*idx+1].sum += a[idx].upd * (mid - constl + 1);
a[2*idx+2].sum += a[idx].upd * (constr - mid);
a[idx].upd = 0;
a[idx].sum = a[2*idx+1].sum + a[2*idx+2].sum;
a[idx].mi = min(a[2*idx+1].mi, a[2*idx+2].mi);
a[idx].ma = max(a[2*idx+1].ma, a[2*idx+2].ma);
}
if(mid<l || r<constl) u(l, r, mid+1, constr, 2*idx+2, v);
else if(constr<l || r<mid+1) u(l, r, constl, mid, 2*idx+1, v);
else {
u(l, r, constl, mid, 2*idx+1, v);
u(l, r, mid+1, constr, 2*idx+2, v);
}
a[idx].mi = min(a[2*idx+1].mi, a[2*idx+2].mi);
a[idx].ma = max(a[2*idx+1].ma, a[2*idx+2].ma);
a[idx].sum = a[2*idx+1].sum + a[2*idx+2].sum;
}
int qu1(int l, int r, int constl, int constr, int idx) {
if(l<=constl && constr<=r) return a[idx].sum;
int mid = (constl+constr) >> 1;
if(a[idx].upd != 0) {
a[2*idx+1].mi += a[idx].upd;
a[2*idx+2].mi += a[idx].upd;
a[2*idx+1].ma += a[idx].upd;
a[2*idx+2].ma += a[idx].upd;
a[2*idx+1].upd += a[idx].upd;
a[2*idx+2].upd += a[idx].upd;
a[2*idx+1].sum += a[idx].upd * (mid - constl + 1);
a[2*idx+2].sum += a[idx].upd * (constr - mid);
a[idx].upd = 0;
a[idx].sum = a[2*idx+1].sum + a[2*idx+2].sum;
a[idx].mi = min(a[2*idx+1].mi, a[2*idx+2].mi);
a[idx].ma = max(a[2*idx+1].ma, a[2*idx+2].ma);
}
if(mid<l || r<constl) return qu1(l, r, mid+1, constr, 2*idx+2);
else if(constr<l || r<mid+1) return qu1(l, r, constl, mid, 2*idx+1);
return qu1(l, r, constl, mid, 2*idx+1) + qu1(l, r, mid+1, constr, 2*idx+2);
}
int qu2(int l, int r, int constl, int constr, int idx) {
if(l<=constl && constr<=r) return a[idx].mi;
int mid = (constl+constr) >> 1;
if(a[idx].upd != 0) {
a[2*idx+1].mi += a[idx].upd;
a[2*idx+2].mi += a[idx].upd;
a[2*idx+1].ma += a[idx].upd;
a[2*idx+2].ma += a[idx].upd;
a[2*idx+1].upd += a[idx].upd;
a[2*idx+2].upd += a[idx].upd;
a[2*idx+1].sum += a[idx].upd * (mid - constl + 1);
a[2*idx+2].sum += a[idx].upd * (constr - mid);
a[idx].upd = 0;
a[idx].sum = a[2*idx+1].sum + a[2*idx+2].sum;
a[idx].mi = min(a[2*idx+1].mi, a[2*idx+2].mi);
a[idx].ma = max(a[2*idx+1].ma, a[2*idx+2].ma);
}
if(mid<l || r<constl) return qu2(l, r, mid+1, constr, 2*idx+2);
else if(constr<l || r<mid+1) return qu2(l, r, constl, mid, 2*idx+1);
return min(qu2(l, r, constl, mid, 2*idx+1), qu2(l, r, mid+1, constr, 2*idx+2));
}
int qu3(int l, int r, int constl, int constr, int idx) {
if(l<=constl && constr<=r) return a[idx].ma;
int mid = (constl+constr) >> 1;
if(a[idx].upd != 0) {
a[2*idx+1].mi += a[idx].upd;
a[2*idx+2].mi += a[idx].upd;
a[2*idx+1].ma += a[idx].upd;
a[2*idx+2].ma += a[idx].upd;
a[2*idx+1].upd += a[idx].upd;
a[2*idx+2].upd += a[idx].upd;
a[2*idx+1].sum += a[idx].upd * (mid - constl + 1);
a[2*idx+2].sum += a[idx].upd * (constr - mid);
a[idx].upd = 0;
a[idx].sum = a[2*idx+1].sum + a[2*idx+2].sum;
a[idx].mi = min(a[2*idx+1].mi, a[2*idx+2].mi);
a[idx].ma = max(a[2*idx+1].ma, a[2*idx+2].ma);
}
if(mid<l || r<constl) return qu3(l, r, mid+1, constr, 2*idx+2);
else if(constr<l || r<mid+1) return qu3(l, r, constl, mid, 2*idx+1);
return max(qu3(l, r, constl, mid, 2*idx+1), qu3(l, r, mid+1, constr, 2*idx+2));
}
int qu4(int l, int r, int constl, int constr, int idx, int val) {
if(l<=constl && constr<=r) {
if(a[idx].mi > val) return -1;
while(constl < constr) {
int mid = (constl + constr) >> 1;
if(a[idx].upd != 0) {
a[2*idx+1].mi += a[idx].upd;
a[2*idx+2].mi += a[idx].upd;
a[2*idx+1].ma += a[idx].upd;
a[2*idx+2].ma += a[idx].upd;
a[2*idx+1].upd += a[idx].upd;
a[2*idx+2].upd += a[idx].upd;
a[2*idx+1].sum += a[idx].upd * (mid - constl + 1);
a[2*idx+2].sum += a[idx].upd * (constr - mid);
a[idx].upd = 0;
a[idx].sum = a[2*idx+1].sum + a[2*idx+2].sum;
a[idx].mi = min(a[2*idx+1].mi, a[2*idx+2].mi);
a[idx].ma = max(a[2*idx+1].ma, a[2*idx+2].ma);
}
if(a[2*idx+1].mi == val) {
idx = 2*idx+1;
constr = mid;
}
else {
idx = 2*idx+2;
constl = mid + 1;
}
}
return (a[idx].mi == val? constl: -1);
}
int mid = (constl + constr) >> 1;
if(a[idx].upd != 0) {
a[2*idx+1].mi += a[idx].upd;
a[2*idx+2].mi += a[idx].upd;
a[2*idx+1].ma += a[idx].upd;
a[2*idx+2].ma += a[idx].upd;
a[2*idx+1].upd += a[idx].upd;
a[2*idx+2].upd += a[idx].upd;
a[2*idx+1].sum += a[idx].upd * (mid - constl + 1);
a[2*idx+2].sum += a[idx].upd * (constr - mid);
a[idx].upd = 0;
a[idx].sum = a[2*idx+1].sum + a[2*idx+2].sum;
a[idx].mi = min(a[2*idx+1].mi, a[2*idx+2].mi);
a[idx].ma = max(a[2*idx+1].ma, a[2*idx+2].ma);
}
if(mid<l || r<constl) {
return qu4(l, r, mid+1, constr, 2*idx+2, val);
}
else if(constr<l || r<mid+1) {
return qu4(l, r, constl, mid, 2*idx+1, val);
}
int omg = qu4(l, r, constl, mid, 2*idx+1, val);
if(omg != -1) return omg;
return qu4(l, r, mid+1, constr, 2*idx+2, val);
}
int qu5(int l, int r, int constl, int constr, int idx, int val) {
if(l<=constl && constr<=r) {
if(a[idx].ma < val) return -1;
while(constl < constr) {
int mid = (constl + constr) >> 1;
if(a[idx].upd != 0) {
a[2*idx+1].mi += a[idx].upd;
a[2*idx+2].mi += a[idx].upd;
a[2*idx+1].ma += a[idx].upd;
a[2*idx+2].ma += a[idx].upd;
a[2*idx+1].upd += a[idx].upd;
a[2*idx+2].upd += a[idx].upd;
a[2*idx+1].sum += a[idx].upd * (mid - constl + 1);
a[2*idx+2].sum += a[idx].upd * (constr - mid);
a[idx].upd = 0;
a[idx].sum = a[2*idx+1].sum + a[2*idx+2].sum;
a[idx].mi = min(a[2*idx+1].mi, a[2*idx+2].mi);
a[idx].ma = max(a[2*idx+1].ma, a[2*idx+2].ma);
}
if(a[2*idx+2].ma == val) {
idx = 2*idx+2;
constl = mid+1;
}
else {
idx = 2*idx+1;
constr = mid;
}
}
return (a[idx].ma == val? constl: -1);
}
int mid = (constl + constr) >> 1;
if(a[idx].upd != 0) {
a[2*idx+1].mi += a[idx].upd;
a[2*idx+2].mi += a[idx].upd;
a[2*idx+1].ma += a[idx].upd;
a[2*idx+2].ma += a[idx].upd;
a[2*idx+1].upd += a[idx].upd;
a[2*idx+2].upd += a[idx].upd;
a[2*idx+1].sum += a[idx].upd * (mid - constl + 1);
a[2*idx+2].sum += a[idx].upd * (constr - mid);
a[idx].upd = 0;
a[idx].sum = a[2*idx+1].sum + a[2*idx+2].sum;
a[idx].mi = min(a[2*idx+1].mi, a[2*idx+2].mi);
a[idx].ma = max(a[2*idx+1].ma, a[2*idx+2].ma);
}
if(mid<l || r<constl) {
return qu5(l, r, mid+1, constr, 2*idx+2, val);
}
else if(constr<l || r<mid+1) {
return qu5(l, r, constl, mid, 2*idx+1, val);
}
int omg = qu5(l, r, mid+1, constr, 2*idx+2, val);
if(omg != -1) return omg;
return qu5(l, r, constl, mid, 2*idx+1, val);
}
public:
void resize(int k) {
stok = k;
a.resize(4*k + 10);
}
void range_add(int l, int r, int v) {
u(l, r, 0, stok, 0, v);
}
int query_sum(int l, int r) {
return qu1(l, r, 0, stok, 0);
}
int query_min(int l, int r) {
return qu2(l, r, 0, stok, 0);
}
int query_max(int l, int r) {
return qu3(l, r, 0, stok, 0);
}
pair<int, int> query_range(int i) {
int val = query_sum(i, i);
int lb = qu4(1, i, 0, stok, 0, val);
int rb = qu5(i, stok, 0, stok, 0, val);
return {lb, rb};
}
};
void solve(int tc) {
int n;
cin >> n;
mast m[n+1];
for(int i=1; i<=n; i++) {
cin >> m[i].height >> m[i].cnt;
}
sort(m+1, m+n+1, cmp);
segtree_dec st;
st.resize(100000);
for(int i=1; i<=n; i++) {
int q = m[i].height - m[i].cnt + 1;
pair<int, int> res = st.query_range(q);
res.second = min(res.second, m[i].height);
st.range_add(q, m[i].height, 1);
int newl = res.second - q + 1;
st.range_add(q, res.second, -1);
st.range_add(res.first, res.first + newl - 1, 1);
}
int ans = 0;
for(int i=1; i<=100000; i++) {
int q = st.query_sum(i, i);
ans += q * (q-1) / 2;
}
cout << ans << "\n";
}
int32_t main(){
ios::sync_with_stdio(0); cin.tie(0);
int t = 1;// cin >> t;
for(int i=1; i<=t; i++) solve(i);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
12748 KB |
Output is correct |
| 2 |
Correct |
12 ms |
12748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
12748 KB |
Output is correct |
| 2 |
Correct |
12 ms |
12748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
12804 KB |
Output is correct |
| 2 |
Correct |
11 ms |
12748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
12748 KB |
Output is correct |
| 2 |
Correct |
12 ms |
12748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
12748 KB |
Output is correct |
| 2 |
Correct |
16 ms |
12876 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
12876 KB |
Output is correct |
| 2 |
Correct |
66 ms |
13480 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
52 ms |
13260 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
107 ms |
13640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
224 ms |
13888 KB |
Output is correct |
| 2 |
Correct |
145 ms |
14916 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
173 ms |
14152 KB |
Output is correct |
| 2 |
Correct |
122 ms |
14868 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
214 ms |
14300 KB |
Output is correct |
| 2 |
Correct |
158 ms |
15412 KB |
Output is correct |
