Submission #331090

#	Time	Username	Problem	Language	Result	Execution time	Memory
331090		lohacho	Sails (IOI07_sails)	C++14	100 / 100	111 ms	14108 KiB

sails

#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 (stderr)

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 / 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