oj.uz

Submission #466373

# Submission time Handle Problem Language Result Execution time Memory
466373 2021-08-19T04:01:09 Z jli12345 Sails (IOI07_sails) C++14
0 / 100
 134 ms 5188 KB 
#include <bits/stdc++.h>
using namespace std;

void fastIO(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
}

int N;

pair<int, int> arr[100100];

long long st[400100];
long long addtag[400100];

void pushdown(int node, int l, int mid, int r){
    st[node*2] += addtag[node]*(mid-l+1);
    st[node*2+1] += addtag[node]*(r-mid);
    addtag[node*2] += addtag[node];
    addtag[node*2+1] += addtag[node];
    addtag[node] = 0;
}

void U(int node, int l, int r, int tl, int tr, int val){
    if (l > tr || r < tl)
        return;
    if (l >= tl && r <= tr){
        st[node] += (long long)(r-l+1)*val;
        addtag[node] += val;
        return;
    }
    int mid = (l+r)/2;
    pushdown(node, l, mid, r);
    U(node*2, l, mid, tl, tr, val);
    U(node*2+1, mid+1, r, tl, tr, val);
    st[node] = st[node*2]+st[node*2+1];
}

long long S(int node, int l, int r, int ind){
    if (l > ind || r < ind)
        return 0;
    if (l == r){
        return st[node];
    }
    int mid = (l+r)/2;
    pushdown(node, l, mid, r);
    return S(node*2, l, mid, ind)+S(node*2+1, mid+1, r, ind);
}

int main(){
    fastIO();
    cin >> N;
    for (int i = 1; i <= N; i++){
        cin >> arr[i].first >> arr[i].second;
    }
    sort(arr+1, arr+1+N);
    int l = 1;
    for (int i = 1; i <= N; i++){
        if (l+arr[i].second-1 <= arr[i].first){
            U(1, 1, 100000, l, l+arr[i].second-1, 1);
            l += arr[i].second;
            if (l == arr[i].first+1)
                l = 1;
        } else {
            U(1, 1, 100000, l, arr[i].first, 1);
            arr[i].second -= (arr[i].first-l+1);
            U(1, 1, 100000, 1, arr[i].second, 1);
            l = arr[i].second+1;
            if (l == arr[i].first+1)
                l = 1;
        }
    }
    long long ans = 0;
    for (int i = 1; i <= 100000; i++){
        long long cnt = S(1, 1, 100000, i);
        ans += (cnt)*(cnt-1)/2;
    }
    cout << ans << "\n";
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 5.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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

Subtask #11
0 / 10.0

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