oj.uz

Submission #709501

# Submission time Handle Problem Language Result Execution time Memory
709501 2023-03-13T18:46:04 Z PoonYaPat Sails (IOI07_sails) C++14
100 / 100
 61 ms 5748 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;

ll ans;
set<pii> s;
int n;
pii a[100001];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    for (int i=1; i<=n; ++i) cin>>a[i].first>>a[i].second;
    sort(a+1,a+n+1);
    s.insert(pii(0,0));

    for (int i=1; i<=n; ++i) {

        auto it=s.upper_bound(pii(a[i].first,-INT_MAX));
        if (it==s.end() || (*it).first!=a[i].first) s.insert(pii(a[i].first,0));

        it=s.upper_bound(pii(a[i].first-a[i].second,-INT_MAX));

        if ((*it).first!=a[i].first-a[i].second) {
            auto it2=it; --it2;
            if ((*it2).second!=-1) s.insert(pii((*it2).first,(*it2).second+1));
            s.insert(pii((*it2).first+a[i].second-a[i].first+(*it).first,-1));
            s.erase(it2);
        }

        if (it!=--s.end()) {
            if ((*it).second!=-1) s.insert(pii((*it).first,(*it).second+1));
            s.erase(it);

            auto it3=s.end(); --it3;
            s.insert(pii((*it3).first,(*it3).second-1));
            s.erase(it3);
        }

        it=s.end(); --it;
        if ((*it).second==0) s.erase(it);
    }

    auto it1=s.begin(), it2=it1++;
    ll h=(*it2).second;
    while (it1!=s.end()) {
        ans+=h*(h-1)*((*it1).first-(*it2).first)/2;
        h+=(*it1).second;
        ++it1; ++it2;
    }
    cout<<ans;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 328 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 328 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 596 KB Output is correct
2 Correct 15 ms 1148 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2876 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2204 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 2612 KB Output is correct
2 Correct 40 ms 3416 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 5748 KB Output is correct
2 Correct 27 ms 2388 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 3964 KB Output is correct
2 Correct 29 ms 2892 KB Output is correct