| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 849500 |
2023-09-14T17:07:55 Z |
fanwen |
Sails (IOI07_sails) |
C++17 |
|
121 ms |
5456 KB |
#include <bits/stdc++.h>
using namespace std;
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
#define REP(i, n) for (int i = 0, _n = n; i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define FORE(i, a, b) for (int i = (a), _b = (b); i < _b; ++i)
#define debug(...) "[" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
template <class A, class B> bool minimize(A &a, B b) { if (a > b) { a = b; return true; } return false; }
template <class A, class B> bool maximize(A &a, B b) { if (a < b) { a = b; return true; } return false; }
template <class T>
struct lazy_segment_tree {
vector <T> it, lazy;
int n;
void modify(int idx, int l, int r, T val) {
it[idx] += val;
lazy[idx] += val;
}
T merge(const T &a, const T &b) {
return max(a, b);
}
void push(int idx, int l, int r) {
if(lazy[idx] == 0) return;
int mid = l + r >> 1;
modify(idx << 1, l, mid, lazy[idx]);
modify(idx << 1 | 1, mid + 1, r, lazy[idx]);
lazy[idx] = 0;
}
void update(int idx, int l, int r, int u, int v, T val) {
if(l > v || r < u) return;
if(l >= u && r <= v) {
modify(idx, l, r, val);
return;
}
push(idx, l, r);
int mid = l + r >> 1;
update(idx << 1, l, mid, u, v, val);
update(idx << 1 | 1, mid + 1, r, u, v, val);
it[idx] = merge(it[idx << 1], it[idx << 1 | 1]);
}
T get(int idx, int l, int r, int u, int v) {
if(l > v || r < u) return 0;
if(l >= u && r <= v) return it[idx];
push(idx, l, r);
int mid = l + r >> 1;
return merge(get(idx << 1, l, mid, u, v), get(idx << 1 | 1, mid + 1, r, u, v));
}
int find(int idx, int l, int r, int val) {
if(it[idx] < val) return n + 1;
if(l == r) return l;
push(idx, l, r);
int mid = l + r >> 1;
int res = find(idx << 1, l, mid, val);
if(res == n + 1) res = find(idx << 1 | 1, mid + 1, r, val);
return res;
}
public :
explicit lazy_segment_tree(int n) :
n(n), lazy(n << 2 | 1, 0), it(n << 2 | 1) {}
void update(int l, int r, T val) {
update(1, 1, n, l, r, val);
}
T get(int l, int r) {
return get(1, 1, n, l, r);
}
T get(int u) {
return get(u, u);
}
int find(int val) {
return find(1, 1, n, val);
}
};
#define fi first
#define se second
const int MAXN = 1e5 + 5;
int N;
pair <int, int> h[MAXN];
void you_make_it(void) {
cin >> N;
FOR(i, 1, N) cin >> h[i].fi >> h[i].se;
sort(h + 1, h + N + 1);
int Max = h[N].fi;
lazy_segment_tree <int> it(Max);
FOR(i, 1, N) {
h[i].fi = Max - h[i].fi + 1;
int a = it.get(h[i].fi + h[i].se - 1), b = it.find(a + 1);
a = max(h[i].fi, it.find(a));
int rem = h[i].se - (a - (h[i].fi));
it.update(h[i].fi, a - 1, 1);
it.update(b - rem, b - 1, 1);
// cout << rem << '\n';
}
long long ans = 0;
FOR(i, 1, Max) {
int x = it.get(i);
ans += 1LL * x * (x - 1) / 2;
// cout << x << " \n"[i == Max];
}
cout << ans;
}
signed main() {
#ifdef LOCAL
freopen("TASK.inp", "r", stdin);
freopen("TASK.out", "w", stdout);
#endif
auto start_time = chrono::steady_clock::now();
cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
you_make_it();
auto end_time = chrono::steady_clock::now();
cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;
return (0 ^ 0);
}
// Dream it. Wish it. Do it.
Compilation message
sails.cpp: In instantiation of 'lazy_segment_tree<T>::lazy_segment_tree(int) [with T = int]':
sails.cpp:107:35: required from here
sails.cpp:21:9: warning: 'lazy_segment_tree<int>::n' will be initialized after [-Wreorder]
21 | int n;
| ^
sails.cpp:20:20: warning: 'std::vector<int> lazy_segment_tree<int>::lazy' [-Wreorder]
20 | vector <T> it, lazy;
| ^~~~
sails.cpp:73:14: warning: when initialized here [-Wreorder]
73 | explicit lazy_segment_tree(int n) :
| ^~~~~~~~~~~~~~~~~
sails.cpp:20:20: warning: 'lazy_segment_tree<int>::lazy' will be initialized after [-Wreorder]
20 | vector <T> it, lazy;
| ^~~~
sails.cpp:20:16: warning: 'std::vector<int> lazy_segment_tree<int>::it' [-Wreorder]
20 | vector <T> it, lazy;
| ^~
sails.cpp:73:14: warning: when initialized here [-Wreorder]
73 | explicit lazy_segment_tree(int n) :
| ^~~~~~~~~~~~~~~~~
sails.cpp: In instantiation of 'int lazy_segment_tree<T>::find(int, int, int, int) [with T = int]':
sails.cpp:89:20: required from 'int lazy_segment_tree<T>::find(int) [with T = int]'
sails.cpp:110:65: required from here
sails.cpp:65:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
65 | int mid = l + r >> 1;
| ~~^~~
sails.cpp: In instantiation of 'void lazy_segment_tree<T>::update(int, int, int, int, int, T) [with T = int]':
sails.cpp:77:15: required from 'void lazy_segment_tree<T>::update(int, int, T) [with T = int]'
sails.cpp:113:36: required from here
sails.cpp:47:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
47 | int mid = l + r >> 1;
| ~~^~~
sails.cpp: In instantiation of 'T lazy_segment_tree<T>::get(int, int, int, int, int) [with T = int]':
sails.cpp:81:19: required from 'T lazy_segment_tree<T>::get(int, int) [with T = int]'
sails.cpp:85:19: required from 'T lazy_segment_tree<T>::get(int) [with T = int]'
sails.cpp:110:45: required from here
sails.cpp:57:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
57 | int mid = l + r >> 1;
| ~~^~~
sails.cpp: In instantiation of 'void lazy_segment_tree<T>::push(int, int, int) [with T = int]':
sails.cpp:64:9: required from 'int lazy_segment_tree<T>::find(int, int, int, int) [with T = int]'
sails.cpp:89:20: required from 'int lazy_segment_tree<T>::find(int) [with T = int]'
sails.cpp:110:65: required from here
sails.cpp:34:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
34 | int mid = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
600 KB |
Output is correct |
| 2 |
Correct |
11 ms |
3416 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
1368 KB |
Output is correct |
| 2 |
Correct |
24 ms |
856 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
1960 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
2904 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
92 ms |
4964 KB |
Output is correct |
| 2 |
Correct |
81 ms |
4948 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
96 ms |
5200 KB |
Output is correct |
| 2 |
Correct |
62 ms |
4652 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
121 ms |
5456 KB |
Output is correct |
| 2 |
Correct |
74 ms |
3160 KB |
Output is correct |
