oj.uz

답안 #849500

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
849500 2023-09-14T17:07:55 Z fanwen Sails (IOI07_sails) C++17
100 / 100
 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;
      |                   ~~^~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 11 ms 3416 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 1368 KB Output is correct
2 Correct 24 ms 856 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 1960 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 2904 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 92 ms 4964 KB Output is correct
2 Correct 81 ms 4948 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 96 ms 5200 KB Output is correct
2 Correct 62 ms 4652 KB Output is correct

Subtask #11
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 121 ms 5456 KB Output is correct
2 Correct 74 ms 3160 KB Output is correct