Submission #713433

#	Time	Username	Problem	Language	Result	Execution time	Memory
713433		LittleOrange	Sails (IOI07_sails)	C++17	100 / 100	209 ms	12376 KiB

sails

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
struct segtree{
    ll n;
    vector<ll> a,b,tag;
    segtree(ll N):n(N){
        a.resize(n<<2,0);
        b.resize(n<<2,0);
        tag.resize(n<<2,0);
    }
    void add(ll i, ll v){
        //cerr << i << " " << v << '\n';
        a[i] += v;
        b[i] += v;
        tag[i] += v;
    }
    void push(ll i){
        if (tag[i]!=0){
            add(i<<1,tag[i]);
            add(i<<1|1,tag[i]);
            tag[i] = 0;
        }
    }
    void pull(ll i){
        a[i] = min(a[i<<1],a[i<<1|1]);
        b[i] = max(b[i<<1],b[i<<1|1]);
    }
    void add(ll i, ll l, ll r, ll ql, ll qr, ll v){
        if (ql<=l&&r<=qr) add(i,v);
        else{
            push(i);
            ll m = l+r>>1;
            if (ql<=m) add(i<<1,l,m,ql,qr,v);
            if (qr>m) add(i<<1|1,m+1,r,ql,qr,v);
            pull(i);
        }
    }
    void add(ll ql, ll qr, ll v){
        //cerr << "add " << ql << " " << qr << " " << v << '\n';
        add(1, 1, n, ql, qr, v);
    }
    ll get(ll i, ll l, ll r, ll x){
        //cerr << "get " << i << " " << l << " " << r << " " << x << "\n";
        if (l == r) return b[i];
        else{
            push(i);
            pull(i);
            ll m = l+r>>1;
            ll ans;
            if (x<=m) ans = get(i<<1,l,m,x);
            else ans = get(i<<1|1,m+1,r,x);
            return ans;
        }
    }
    ll get(ll x){
        return get(1,1,n,x);
    }
    ll left(ll i, ll l, ll r, ll x){
        if (l == r) return l;
        else{
            push(i);
            pull(i);
            ll m = l+r>>1;
            ll ans;
            if (a[i<<1]<=x&&b[i<<1]>=x) ans = left(i<<1,l,m,x);
            else ans = left(i<<1|1,m+1,r,x);
            return ans;
        }
    }
    ll left(ll x){
        return left(1,1,n,x);
    }
    ll right(ll i, ll l, ll r, ll x){
        if (l == r) return l;
        else{
            push(i);
            pull(i);
            ll m = l+r>>1;
            ll ans;
            if (b[i<<1|1]<x||a[i<<1|1]>x) ans = right(i<<1,l,m,x);
            else ans = right(i<<1|1,m+1,r,x);
            return ans;
        }
    }
    ll right(ll x){
        return right(1,1,n,x);
    }
    ll query(ll i, ll l, ll r){
        if(l == r) return a[i]*(a[i]-1)/2;
        else{
            push(i);
            ll m = l+r>>1;
            return query(i<<1,l,m)+query(i<<1|1,m+1,r);
        }
    }
    ll query(){
        return query(1,1,n);
    }
};
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    ll n;
    cin >> n;
    vector<pair<ll,ll>> a(n);
    for(auto &o : a) cin >> o.first >> o.second;
    sort(a.begin(),a.end());
    segtree t(100000);
    for(auto &o : a){
        //cerr << "solve " << o.first << " " << o.second << '\n';
        ll x = o.first-o.second+1;
        ll v = t.get(x);
        ll l = t.left(v);
        ll r = t.right(v);
        t.add(l,o.first,1);
        if (l<x){
            ll w = min(r,o.first)-(x-l)+1;
            t.add(w,min(r,o.first),-1);
        }
    }
    cout << t.query() << '\n';
}

Compilation message (stderr)

sails.cpp: In member function 'void segtree::add(ll, ll, ll, ll, ll, ll)':
sails.cpp:33:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |             ll m = l+r>>1;
      |                    ~^~
sails.cpp: In member function 'll segtree::get(ll, ll, ll, ll)':
sails.cpp:49:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |             ll m = l+r>>1;
      |                    ~^~
sails.cpp: In member function 'll segtree::left(ll, ll, ll, ll)':
sails.cpp:64:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |             ll m = l+r>>1;
      |                    ~^~
sails.cpp: In member function 'll segtree::right(ll, ll, ll, ll)':
sails.cpp:79:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   79 |             ll m = l+r>>1;
      |                    ~^~
sails.cpp: In member function 'll segtree::query(ll, ll, ll)':
sails.cpp:93:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   93 |             ll m = l+r>>1;
      |                    ~^~

• 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