oj.uz

답안 #837583

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
837583 2023-08-25T12:29:10 Z Andrey Sails (IOI07_sails) C++14
0 / 100
 101 ms 11648 KB 
#include<bits/stdc++.h>
using namespace std;

vector<int> seg(1000001);
vector<int> sb(800001);
vector<int> big(800001);
int yo;

void upd(int l, int r, int ql, int qr, int x, int br) {
    if(l == ql && r == qr) {
        seg[x]+=br;
        big[x]+=br;
        sb[x]+=br*(r-l+1);
        return;
    }
    int m = (l+r)/2;
    if(qr <= m) {
        upd(l,m,ql,qr,x*2+1,br);
    }
    else if(ql > m) {
        upd(m+1,r,ql,qr,x*2+2,br);
    }
    else {
        upd(l,m,ql,m,x*2+1,br);
        upd(m+1,r,m+1,qr,x*2+2,br);
    }
    big[x] = min(big[x*2+1],big[x*2+2])+seg[x];
    sb[x] = sb[x*2+1]+sb[x*2+2]+seg[x]*(r-l+1);
}

int calc(int l, int r, int ql, int qr, int x, int br) {
    if(l == ql && r == qr) {
        return sb[x]+br*(r-l+1);
    }
    int m = (l+r)/2;
    if(qr <= m) {
        return calc(l,m,ql,qr,x*2+1,br+seg[x]);
    }
    else if(ql > m) {
        return calc(m+1,r,ql,qr,x*2+2,br+seg[x]);
    }
    else {
        return calc(l,m,ql,m,x*2+1,br+seg[x])+calc(m+1,r,m+1,qr,x*2+2,br+seg[x]);
    }
}

int banana(int a, int l, int r, int x, int br) {
    if(l == r) {
        return l;
    }
    int m = (l+r)/2;
    br+=seg[x];
    if(br+big[x*2+2] < a || m+1 > yo) {
        return banana(a,l,m,x*2+1,br);
    }
    else {
        return banana(a,m+1,r,x*2+2,br);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    long long n,a,b,ans = 0;
    cin >> n;
    vector<pair<int,int>> haha(0);
    vector<int> yay(0);
    for(int i = 0; i < n; i++) {
        cin >> a >> b;
        haha.push_back({a,b});
    }
    sort(haha.begin(),haha.end());
    upd(0,200000,0,0,0,1000000);
    for(int i = 0; i < n; i++) {
        a = haha[i].first;
        b = haha[i].second;
        yo = a;
        ans+=calc(0,200000,a-b+1,a,0,0);
        int c = calc(0,200000,a-b+1,a-b+1,0,0);
        int p = banana(c,0,200000,0,0);
        if(p+1 < a) {
            upd(0,200000,p+1,a,0,1);
        }
        int p1 = banana(c+1,0,200000,0,0);
        if(p1+1 <= p1+b-(a-p)) {
            upd(0,200000,p1+1,p1+b-(a-p),0,1);
        }
    }
    cout << ans;
    return 0;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 10452 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 10452 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 10404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 10452 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 10452 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 10580 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 34 ms 10836 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 47 ms 11096 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 82 ms 11648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 94 ms 11604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 101 ms 11604 KB Output isn't correct
2 Halted 0 ms 0 KB -