oj.uz

Submission #849352

# Submission time Handle Problem Language Result Execution time Memory
849352 2023-09-14T14:09:22 Z phoenix0423 Sails (IOI07_sails) C++17
100 / 100
 78 ms 3800 KB 
#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.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 444 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 600 KB Output is correct
2 Correct 23 ms 988 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2052 KB Output is correct

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 1528 KB Output is correct
2 Correct 54 ms 2900 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 3800 KB Output is correct
2 Correct 45 ms 1468 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 2132 KB Output is correct
2 Correct 62 ms 2392 KB Output is correct