Submission #849352

#	Time	Username	Problem	Language	Result	Execution time	Memory
849352		phoenix0423	Sails (IOI07_sails)	C++17	100 / 100	78 ms	3800 KiB

sails

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#pragma GCC optimize("Ofast")
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
#define all(v) v.begin(), v.end()
const int maxn = 1e5 + 5;
int BIT[maxn];
void upd(int pos, int val){
    pos++;
    while(pos < maxn){
        BIT[pos] += val;
        pos += lowbit(pos);
    }
}
int qry(int pos){
    pos++;
    int ret = 0;
    while(pos > 0){
        ret += BIT[pos];
        pos -= lowbit(pos);
    }
    return ret;
}
struct info{
    int h, k;
    info(){}
    info(int _h, int _k) : h(_h), k(_k){}
    bool operator < (const info& other) const{
        return h < other.h || (h == other.h && k < other.k);
    }
};
istream &operator>>(istream &s, info & q){
    s >> q.h >> q.k;
    return s;
}
int main(void){
//    fastio;
    int n;
    cin>>n;
    vector<info> a(n);
    for(int i = 0; i < n; i++) cin>>a[i];
    sort(a.begin(), a.end());
    set<int> s;
    s.insert(0);
    for(int i = 0; i < n; i++){
        auto [h, k] = a[i];
        auto idx = s.upper_bound(h - k);
        idx--;
        //idx = first change point smaller than h - k
        if(idx == prev(s.end())){
            int x = *idx;
            if(qry(x) == 1) s.erase(idx);
            s.insert(x + k);
            upd(x + 1, 1);
            upd(x + k + 1, -1);
        }
        else if(*idx == h - k){
            upd(h - k + 1, 1);
            upd(h + 1, -1);
            if(qry(h - k + 1) == qry(h - k)) s.erase(idx);
            if(h != *prev(s.end())) s.insert(h);
        }
        else{
            auto nxt = next(idx);
            upd(*nxt + 1, 1);
            upd(h + 1, -1);
            int left = k - (h - *nxt);
            upd(*idx + 1, 1);
            upd(*idx + left + 1, -1);
            s.insert(*idx + left);
            if(h != *prev(s.end())) s.insert(h);
            if(qry(*nxt + 1) == qry(*nxt)) s.erase(nxt);
            if(qry(*idx + 1) == qry(*idx)) s.erase(idx);
        }
    }
    ll pre = 0;
    ll ans = 0;
    for(auto x : s){
        ll cnt = qry(x);
        ans += ll(x - pre) * cnt * (cnt - 1) / 2;
        pre = x;
    }
    cout<<ans<<"\n";
}

• 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