oj.uz

Submission #713433

# Submission time Handle Problem Language Result Execution time Memory
713433 2023-03-22T02:33:18 Z LittleOrange Sails (IOI07_sails) C++17
100 / 100
 209 ms 12376 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9660 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9668 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9660 KB Output is correct
2 Correct 8 ms 9684 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9684 KB Output is correct
2 Correct 8 ms 9684 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 9804 KB Output is correct
2 Correct 59 ms 10488 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 10520 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 11052 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 11704 KB Output is correct
2 Correct 140 ms 11852 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 12156 KB Output is correct
2 Correct 133 ms 11868 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 12376 KB Output is correct
2 Correct 134 ms 12232 KB Output is correct