oj.uz

Submission #331090

# Submission time Handle Problem Language Result Execution time Memory
331090 2020-11-27T10:09:30 Z lohacho Sails (IOI07_sails) C++14
100 / 100
 111 ms 14108 KB 
#include <bits/stdc++.h>

using namespace std;

using LL = long long;
const LL MOD = (LL)1e18 + 7;
const LL NS = (LL)1e5 + 4;
LL N;
LL A[NS], B[NS];
LL a[NS], pre[NS];
LL cro[NS], top;
pair<LL, LL> line[NS];
vector<vector<vector<LL>>> bk;
LL ans[NS];

inline LL getcr(pair<LL, LL> f, pair<LL, LL> s){
    return (f.second - s.second) / (s.first - f.first) + ((f.second - s.second) % (s.first - f.first) > 0);
}

void push(LL f, LL s){
    line[++top] = {f, s};
    if(top > 1){
        cro[top] = getcr(line[top], line[top - 1]);
    }
    else{
        cro[top] = -MOD;
    }
    vector<vector<LL>> nps;
    while(top >= 3 && cro[top] <= cro[top - 1]){
        nps.push_back({line[top - 1].first, line[top - 1].second, cro[top - 1]});
        line[top - 1] = line[top];
        --top;
        cro[top] = getcr(line[top], line[top - 1]);
    }
    bk.push_back(nps);
}

void ret(){
    vector<vector<LL>> now = bk.back();
    bk.pop_back(), --top;
    while((LL)now.size()){
        line[++top] = {now.back()[0], now.back()[1]};
        cro[top] = now.back()[2];
        now.pop_back();
    }
}

LL get(LL x){
    LL pos = lower_bound(cro + 1, cro + top + 1, x + 1) - cro - 1;
    return line[pos].first * x + line[pos].second;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    for(LL i = 1; i <= N; ++i){
        cin >> A[i] >> B[i];
        ++a[A[i] - B[i] + 1], --a[A[i] + 1];
    }
    for(LL i = 1; i < NS; ++i){
        a[i] += a[i - 1];
        pre[i] = a[i] + pre[i - 1];
    }
    for(LL i = NS - 1; i >= 1; --i){
        push(i, -pre[i]);
    }
//    for(int i = 1; i <= top; ++i){
//        cout << line[i].first << ' ' << line[i].second << ' ' << cro[i] << endl;
//    }
    for(LL i = 1; i < NS; ++i){
        LL s = 0, e = NS, mid;
        while(s < e){
            mid = (s + e) >> 1;
//            cout << i << ' ' << mid << ' ' << get(mid) << endl;
            if(get(mid) >= -pre[i - 1] + mid * (i - 1)){
                e = mid;
            }
            else{
                s = mid + 1;
            }
        }
//        cout << s << endl;
        ans[i] = s;
        pre[i] += s - a[i];
        a[i + 1] -= (s - a[i]);
        a[i] = s;
        ret();
    }
    LL out = 0;
    for(LL i = 0; i < NS; ++i){
        out += ans[i] * (ans[i] - 1) / 2;
    }
    cout << out;
    return 0;
}

Compilation message

sails.cpp: In function 'int main()':
sails.cpp:86:18: warning: iteration 100002 invokes undefined behavior [-Waggressive-loop-optimizations]
   86 |         a[i + 1] -= (s - a[i]);
      |         ~~~~~~~~~^~~~~~~~~~~~~
sails.cpp:71:21: note: within this loop
   71 |     for(LL i = 1; i < NS; ++i){
      |                   ~~^~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 11376 KB Output is correct
2 Correct 38 ms 11400 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 11292 KB Output is correct
2 Correct 47 ms 11428 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 11292 KB Output is correct
2 Correct 38 ms 11292 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 11396 KB Output is correct
2 Correct 53 ms 11292 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 11548 KB Output is correct
2 Correct 45 ms 12060 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 11036 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 12316 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 13280 KB Output is correct
2 Correct 88 ms 13596 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 11932 KB Output is correct
2 Correct 57 ms 13468 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 13596 KB Output is correct
2 Correct 61 ms 14108 KB Output is correct