Submission #466373

#	Time	Username	Problem	Language	Result	Execution time	Memory
466373		jli12345	Sails (IOI07_sails)	C++14	0 / 100	134 ms	5188 KiB

sails

#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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 5
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10