Submission #713628

#	Time	Username	Problem	Language	Result	Execution time	Memory
713628		ssense	Sails (IOI07_sails)	C++14	100 / 100	230 ms	15192 KiB

sails

#include <bits/stdc++.h>
#define startt ios_base::sync_with_stdio(false);cin.tie(0);
typedef long long  ll;
using namespace std;
#define vint vector<int>
#define all(v) v.begin(), v.end()
#define MOD 1000000007
#define MOD2 998244353
#define MX 1000000000
#define MXL 1000000000000000000
#define PI (ld)2*acos(0.0)
#define pb push_back
#define sc second
#define fr first
#define int long long
#define endl '\n'
#define ld long double
#define NO cout << "NO" << endl
#define YES cout << "YES" << endl
int ceildiv(int one, int two) {if (one % two == 0) {return one / two;}else {return one / two + 1;}} int power(int n, int pow, int m) {if (pow == 0) return 1;if (pow % 2 == 0) {ll x = power(n, pow / 2, m);return (x * x) % m;}else return (power(n, pow - 1, m) * n) % m;} int gcd(int a, int b) { if (!b)return a; return gcd(b, a % b);} int factorial(int n, int mod) {if (n > 1)return (n * factorial(n - 1, mod)) % mod; else return 1;} int lcm(int a, int b) {return (a * b) / gcd(a, b);} vector<int> read(int n) {vector<int> a; for (int i = 0; i < n; i++) { int x; cin >> x; a.pb(x);} return a;}struct prefix_sum{vint pref;void build(vint a){pref.pb(0);for(int i = 0; i < a.size(); i++){pref.pb(pref.back()+a[i]);}}int get(int l, int r){return pref[r]-pref[l-1];}};//mesanu

template<typename T>
struct LazySegmentTree{
    int n;
    vector<T> t, lazy, a;
    T neutral, lazy_neutral;
    function<T(const T&, const T&)> merge;
    function<T(const T&, const T&)> upd;
    
    bool range_modif = false;
    LazySegmentTree(int _n, T _neutral, T _lazy_neutral, const function<T(const T&, const T&)> &_merge, const function<T(const T&, const T&)> &_upd, bool _range_modif){
        range_modif = _range_modif;
        init(_n, _neutral, _lazy_neutral, _merge, _upd);
    }
    LazySegmentTree(vector<T> _a, T _neutral, T _lazy_neutral, const function<T(const T&, const T&)> &_merge, const function<T(const T&, const T&)> &_upd, bool _range_modif){
        range_modif = _range_modif, a = _a;
        int _n = (int)a.size();
        init(_n, _neutral, _lazy_neutral, _merge, _upd);
        build(1, 0, n - 1);
    }
    
    void init(int _n, T _neutral, T _lazy_neutral, const function<T(const T&, const T&)> &_merge, const function<T(const T&, const T&)> &_upd){
        n = _n, neutral = _neutral, lazy_neutral = _lazy_neutral, merge = _merge, upd = _upd;
        t.assign(4 * n, neutral);
        lazy.assign(4 * n, lazy_neutral);
    }
    
    void build(int i, int l, int r){
        if(l == r){
            t[i] = a[l];
            return;
        }
        
        int mid = (l + r) >> 1;
        build(2 * i, l, mid);
        build(2 * i + 1, mid + 1, r);
        
        t[i] = merge(t[2 * i], t[2 * i + 1]);
    }
    
    void push(int i, int l, int r){
        if(lazy[i].f == -2)return;
        
        t[i] = upd(t[i], lazy[i]);
        
        if(l != r){
            lazy[2 * i] = upd(lazy[2 * i], lazy[i]);
            lazy[2 * i + 1] = upd(lazy[2 * i + 1], lazy[i]);
        }
        lazy[i] = lazy_neutral;
    }
    
    void modif(int i, int l, int r, int tl, int tr, T val){
        push(i, l, r);
        if(l > tr || r < tl)return;
        
        if(l >= tl && r <= tr){
            lazy[i] = upd(lazy[i], val);
            push(i, l, r);
            return;
        }
        
        int mid = (l + r) >> 1;
        
        modif(2 * i, l, mid, tl, tr, val);
        modif(2 * i + 1, mid + 1, r, tl, tr, val);
        
        t[i] = merge(t[2 * i], t[2 * i + 1]);
    }
    T query(int i, int l, int r, int tl, int tr){
        push(i, l, r);
        if(l > tr || r < tl)return neutral;
        if(l >= tl && r <= tr)return t[i];
        
        int mid = (l + r) >> 1;
        
        T left = query(2 * i, l, mid, tl, tr);
        T right = query(2 * i + 1, mid + 1, r, tl, tr);
        
        return merge(left, right);
    }
    
    void modif(int l, int r, T val){
        modif(1, 0, n - 1, l, r, val);
    }
    void modif(int poz, T val){
        modif(1, 0, n - 1, poz, poz, val);
    }
    T query(int l, int r){
        return query(1, 0, n - 1, l, r);
    }
    T query(int poz){
        return query(1, 0, n - 1, poz, poz);
    }
    //n, neutral, lazy neutral, merge, upd, bool range update
};

struct node
{
    int f, l;
};

node mg(node a, node b)
{
    node temp;
    if(a.f == -1){temp.f = b.f;}
    else{temp.f = a.f;}
    temp.l = max(a.l, b.l);
    return temp;
}

node upd(node a, node b)
{
    return b;
}

const int N = 100000;

void solve()
{
    int n;
    cin >> n;
    vector<pair<int, int>> a(n);
    node temp, temp2;
    temp.f = -2;temp.l = -2;
    temp2.f = -1; temp2.l = -1;
    LazySegmentTree<node> st(N+5, temp2, temp, mg, upd, false);
    for(int i = 0; i < n; i++)
    {
        cin >> a[i].fr >> a[i].sc;
        
    }
    vector<int> dif(N+5);
    temp.f = -1; temp.l = -1;
    st.modif(0, N, temp);
    sort(all(a));
    int range = 0;
    for(int i = 0; i < n; i++)
    {
        range = a[i].fr-1;
        int now_idx = range-a[i].sc+1;
        if(now_idx == 0){
            dif[range]++;
            temp.f = range;temp.l = range;
            st.modif(range, temp);
            continue;
        }
        if(dif[now_idx-1] != 0)
        {
            dif[now_idx-1]--;
            if(dif[now_idx-1] == 0)
            {
                temp.f = -1;temp.l = -1;
                st.modif(now_idx-1, temp);
            }
            dif[range]++;
            temp.f = range;temp.l = range;
            st.modif(range, temp);
            continue;
        }
        int now1 = st.query(0, now_idx-1).l;
        int now2 = st.query(now_idx, range).f;
        int already = a[i].sc;
        if(now2 > -1)
        {
            dif[now2]--;
            if(dif[now2] == 0)
            {
                temp.f = -1;temp.l = -1;
                st.modif(now2, temp);
            }
            dif[range]++;
            temp.f = range;temp.l = range;
            st.modif(range, temp);
            already-=range-now2;
        }
        if(now1 == -1)
        {
            dif[already-1]++;
            temp.f = already-1;temp.l = already-1;
            st.modif(already-1, temp);
        }
        else
        {
            dif[now1]--;
            if(dif[now1] == 0)
            {
                temp.f = -1;temp.l = -1;
                st.modif(now1, temp);
            }
            dif[now1+already]++;
            temp.f = now1+already;temp.l = now1+already;
            st.modif(now1+already, temp);
        }
    }
    long long ans = 0;
    int now = 0;
    for(int i = N; i >= 0; i--)
    {
        now+=dif[i];
        ans+=now*(now-1)/2;
    }
    cout << ans << endl;
}

int32_t main(){
    startt
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
}
/*
6
3 2
5 3
4 1
2 1
4 3
3 2
*/

Compilation message (stderr)

sails.cpp: In member function 'void prefix_sum::build(std::vector<long long int>)':
sails.cpp:20:667: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 | int ceildiv(int one, int two) {if (one % two == 0) {return one / two;}else {return one / two + 1;}} int power(int n, int pow, int m) {if (pow == 0) return 1;if (pow % 2 == 0) {ll x = power(n, pow / 2, m);return (x * x) % m;}else return (power(n, pow - 1, m) * n) % m;} int gcd(int a, int b) { if (!b)return a; return gcd(b, a % b);} int factorial(int n, int mod) {if (n > 1)return (n * factorial(n - 1, mod)) % mod; else return 1;} int lcm(int a, int b) {return (a * b) / gcd(a, b);} vector<int> read(int n) {vector<int> a; for (int i = 0; i < n; i++) { int x; cin >> x; a.pb(x);} return a;}struct prefix_sum{vint pref;void build(vint a){pref.pb(0);for(int i = 0; i < a.size(); i++){pref.pb(pref.back()+a[i]);}}int get(int l, int r){return pref[r]-pref[l-1];}};//mesanu
      |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         ~~^~~~~~~~~~

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