Submission #466377

#	Time	Username	Problem	Language	Result	Execution time	Memory
466377		jli12345	Sails (IOI07_sails)	C++14	100 / 100	280 ms	10344 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 stmax[400100];
long long stmin[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);
    stmin[node*2] += addtag[node];
    stmin[node*2+1] += addtag[node];
    stmax[node*2] += addtag[node];
    stmax[node*2+1] += addtag[node];
    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;
        stmin[node] += val;
        stmax[node] += 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];
    stmin[node] = min(stmin[node*2], stmin[node*2+1]);
    stmax[node] = max(stmax[node*2], stmax[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);
}

long long lb(int node, int l, int r, int val){
    if (l == r)
        return l;
    int mid = (l+r)/2;
    pushdown(node, l, mid, r);
    if (stmin[node*2] <= val){
        return lb(node*2, l, mid, val);
    } else {
        return lb(node*2+1, mid+1, r, val);
    }
}

long long rb(int node, int l, int r, int val){
    if (l == r)
        return l;
    int mid = (l+r)/2;
    pushdown(node, l, mid, r);
    if (stmax[node*2+1] >= val){
        return rb(node*2+1, mid+1, r, val);
    } else {
        return rb(node*2, l, mid, val);
    }
}

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);
    //for (int i = 1; i <= N; i++)
        //cout << arr[i].first << " " << arr[i].second << "\n";
    for (int i = 1; i <= N; i++){
        int val = S(1, 1, 100000, arr[i].first-arr[i].second+1);
        int l = lb(1, 1, 100000, val);
        int r = min((long long)arr[i].first, rb(1, 1, 100000, val));
        //cout << val << " " << l << " " << r << "\n";
        if (r < arr[i].first)
            U(1, 1, 100000, r+1, arr[i].first, 1);
        U(1, 1, 100000, l, l+arr[i].second-(arr[i].first-r)-1, 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: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10