oj.uz

Submission #466427

# Submission time Handle Problem Language Result Execution time Memory
466427 2021-08-19T08:41:56 Z FatihSolak Sails (IOI07_sails) C++17
5 / 100
 184 ms 3520 KB 
#include <bits/stdc++.h>
#define N 200005
#define int long long
using namespace std;
struct BIT{
    vector<int> bit;
    int n;
    BIT(int size){
        n = size+1;
        bit.assign(n,0);
    }
    void upd(int pos,int val){
        for(;pos > 0;pos -= pos&-pos){
            bit[pos] += val;
        }
    }
    int get(int pos){
        int ret = 0;
        for(;pos < n;pos += pos&-pos){
            ret += bit[pos];
        }
        return ret;
    }
    int get(int l,int r){
        return get(r) - get(l-1);
    }
};
int n;
int h[N],k[N];
vector<int> v;
int ans = 0;
bool ck(int x){
    int pos = 1;
    ans = 0;
    BIT bt(1e5);
    for(int i=0;i<n;i++){
        while(pos <= n && bt.get(pos) >= x)pos++;
        if(pos == n+1)return 0;
        if(pos-1 > h[v[i]] - k[v[i]])return 0;
        bt.upd(pos + k[v[i]] - 1,1);
    }
    for(int i=1;i<=1e5;i++){
        //cout << i << " " << bt.get(i) << endl;
        ans += min(bt.get(i),x) * (min(bt.get(i),x) - 1)/2; 
    }
    return 1;
}
void solve(){
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> h[i] >> k[i];
        v.push_back(i);
    }
    sort(v.begin(),v.end(),[&](int a,int b){
        return (h[a] - k[a]) < (h[b] - k[b]);
    });
    int l = 1,r = 1e5;
    while(l < r){
        int m = (l+r)/2;
        if(ck(m)){
            r = m;
        }
        else l = m+1;
    }
    ck(l);
    cout << ans << endl;
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef Local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    #ifdef Local
    cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 5.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 1956 KB Output isn't correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 101 ms 2432 KB Output isn't correct

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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

Subtask #11
0 / 10.0

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