Submission #849446

#	Time	Username	Problem	Language	Result	Execution time	Memory
849446		fanwen	Sails (IOI07_sails)	C++17	15 / 100	22 ms	8536 KiB

sails

#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;
    	push(idx, l, r);
    	if(l == r) return l;
    	int mid = l + r >> 1;
    	return (it[idx << 1] >= val ? find(idx << 1, l, mid, val) : find(idx << 1 | 1, mid + 1, r, val));
    }
 
public :
    
    explicit lazy_segment_tree(int n) : 
        n(n), lazy(n << 2 | 1, {}), 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) - 1;
    	a = max(h[i].fi, it.find(a));
    	if(a > h[i].fi) it.update(h[i].fi, a - 1, 1);
    	int rem = h[i].se - (a - (h[i].fi));
    	it.update(b - rem + 1, b, 1);
    	// cout << a << " " << b << " " << h[i].fi << " " << h[i].se << endl;
    }
    long long ans = 0;
    FOR(i, 1, Max) {
    	int x = it.get(i);
    	ans += 1LL * x * (x - 1) / 2;
    }
    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 (stderr)

sails.cpp: In instantiation of 'lazy_segment_tree<T>::lazy_segment_tree(int) [with T = int]':
sails.cpp:105: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:71:14: warning:   when initialized here [-Wreorder]
   71 |     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:71:14: warning:   when initialized here [-Wreorder]
   71 |     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:87:17:   required from 'int lazy_segment_tree<T>::find(int) [with T = int]'
sails.cpp:108:62:   required from here
sails.cpp:65:18: 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:75:15:   required from 'void lazy_segment_tree<T>::update(int, int, T) [with T = int]'
sails.cpp:110:49:   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:79:19:   required from 'T lazy_segment_tree<T>::get(int, int) [with T = int]'
sails.cpp:83:19:   required from 'T lazy_segment_tree<T>::get(int) [with T = int]'
sails.cpp:108:42:   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:63:6:   required from 'int lazy_segment_tree<T>::find(int, int, int, int) [with T = int]'
sails.cpp:87:17:   required from 'int lazy_segment_tree<T>::find(int) [with T = int]'
sails.cpp:108:62:   required from here
sails.cpp:34:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |         int mid = l + r >> 1;
      |                   ~~^~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 5
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10