oj.uz

Submission #849343

# Submission time Handle Problem Language Result Execution time Memory
849343 2023-09-14T14:01:39 Z phoenix0423 Sails (IOI07_sails) C++17
25 / 100
 82 ms 4624 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(*idx != 0) s.erase(idx);
            if(h != a[i - 1].h) 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 != a[i - 1].h) s.insert(h);
            if(qry(*nxt + 1) == qry(*nxt)) s.erase(nxt);
            if(*idx != 0) s.erase(idx);
        }
    }
    ll pre = 0;
    ll ans = 0;
    for(auto x : s){
        ll cnt = qry(x);
        ans += (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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 ms 368 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

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

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 2028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 2624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 4624 KB Output is correct
2 Correct 49 ms 2128 KB Output is correct

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 79 ms 3412 KB Output isn't correct
2 Halted 0 ms 0 KB -