oj.uz

Submission #291855

# Submission time Handle Problem Language Result Execution time Memory
291855 2020-09-05T21:31:56 Z Kastanda Sails (IOI07_sails) C++11
100 / 100
 120 ms 7848 KB 
// M
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct CHT
{
        typedef pair < ll , ll > Line;
        vector < pair < ll , Line > > A;
        vector < vector < pair < ll , Line > > > U;
        ll INF = 1e18;
        inline void Add(Line X)
        {
                vector < pair < ll , Line > > nwu;
                while (A.size() && Intersection(A.back().second, X) <= A.back().first)
                        nwu.push_back(A.back()), A.pop_back();
                if (A.size())
                        A.push_back({Intersection(A.back().second, X), X});
                else
                        A.push_back({-INF, X});
                U.push_back(nwu);
        }
        inline ll GetMax(ll X)
        {
                int lb = upper_bound(A.begin(), A.end(), pair < ll , Line > {X, {INF, INF}}) - A.begin() - 1;
                return (A[lb].second.first * X + A[lb].second.second);
        }
        inline ll Intersection(Line X, Line Y)
        {
                if (X.first == Y.first)
                        return X.second <= Y.second ? -INF : INF;
                return ((X.second - Y.second) / (Y.first - X.first)) + ((X.second - Y.second) % (Y.first - X.first) > 0);
        }
        inline void Undo()
        {
                assert(A.size() && U.size());
                vector < pair < ll , Line > > nwu = U.back();
                U.pop_back(); A.pop_back();
                while (nwu.size())
                        A.push_back(nwu.back()), nwu.pop_back();
        }
};
const int N = 100005;
int n, H[N], K[N], C[N];
ll PS[N];
CHT Cht;
int main()
{
        scanf("%d", &n);
        for (int i = 1; i <= n; i ++)
                scanf("%d%d", &H[i], &K[i]);

        for (int i = 1; i <= n; i ++)
                C[H[i] - K[i] + 1] ++, C[H[i] + 1] --;
        for (int i = 1; i < N; i ++)
                C[i] += C[i - 1];
        for (int i = 1; i < N; i ++)
                PS[i] = PS[i - 1] + C[i];
        for (int i = N - 1; i; i --)
                Cht.Add({-i, PS[i]});

        for (int i = 1; i + 1 < N; i ++)
        {
                int le = max(C[i], 0) - 1, ri = n, md;
                while (ri - le > 1)
                {
                        md = (le + ri) >> 1;
                        if (Cht.GetMax(md) <= PS[i - 1] - (ll)md * (i - 1))
                                ri = md;
                        else
                                le = md;
                }
                PS[i] += ri - C[i];
                C[i + 1] -= ri - C[i];
                C[i] = ri;
                Cht.Undo();
        }
        for (int i = 2; i < N; i ++)
                assert(C[i - 1] >= C[i]);
        ll tot = 0;
        for (int i = 1; i < N; i ++)
                tot += (ll)C[i] * (C[i] - 1) / 2;
        printf("%lld\n", tot);
        return 0;
}

Compilation message

sails.cpp: In function 'int main()':
sails.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   48 |         scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
sails.cpp:50:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   50 |                 scanf("%d%d", &H[i], &K[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6960 KB Output is correct
2 Correct 23 ms 6960 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 6960 KB Output is correct
2 Correct 25 ms 6952 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 6960 KB Output is correct
2 Correct 27 ms 6960 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 7212 KB Output is correct
2 Correct 36 ms 6960 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 7088 KB Output is correct
2 Correct 39 ms 7312 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 7848 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 7336 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 7652 KB Output is correct
2 Correct 68 ms 7848 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 7376 KB Output is correct
2 Correct 51 ms 7720 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 7768 KB Output is correct
2 Correct 55 ms 7720 KB Output is correct