Submission #1262101

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262101		papaulo	Sails (IOI07_sails)	C++20	100 / 100	122 ms	4356 KiB

sails

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int val, lazy;
    Node(int v) : val(v), lazy(0) {}
    Node() : Node(0) {}
    Node operator+(const Node &n) {
        return Node(min(this->val, n.val));
    }
};

#define MAXN 100100
pair<int, int> arr[MAXN];
Node seg[4*MAXN];

void build(int n, int l, int r) {
    if(l==r) seg[n]=Node();
    else {
        int mid=(l+r)/2;
        build(2*n, l, mid);
        build(2*n+1, mid+1, r);
        seg[n]=seg[2*n]+seg[2*n+1];
    }
}

void lazyPropagation(int n, int l, int r) {
    seg[n].val+=seg[n].lazy;
    if(l<r) {
        seg[2*n].lazy+=seg[n].lazy;
        seg[2*n+1].lazy+=seg[n].lazy;
    }
    seg[n].lazy=0;
}

void update(int n, int l, int r, int p, int q, int v) {
    if(l>q||p>r) {
        lazyPropagation(n, l, r);
        return;
    }
    if(l>=p&&r<=q) {
        seg[n].lazy+=v;
        lazyPropagation(n, l, r);
        return;
    }
    int mid=(l+r)/2;
    lazyPropagation(n, l, r);
    update(2*n, l, mid, p, q, v);
    update(2*n+1, mid+1, r, p, q, v);
    seg[n]=seg[2*n]+seg[2*n+1];
}

int query(int n, int l, int r, int i) {
    lazyPropagation(n, l, r);
    if(l==r) return seg[n].val;
    int mid=(l+r)/2;
    if(i<=mid) return query(2*n, l, mid, i);
    return query(2*n+1, mid+1, r, i);
}

int fstidx(int n, int l, int r, int v) {
    lazyPropagation(n, l, r);
    if(seg[n].val>v) return r+1;
    if(l==r) return l;
    int mid=(l+r)/2;
    int lq=fstidx(2*n, l, mid, v);
    if(lq<=mid) return lq;
    return fstidx(2*n+1, mid+1, r, v);
}

#define MAXV 100000

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for(int i=0;i<n;i++) cin >> arr[i].first >> arr[i].second;
    sort(arr, arr+n);
    build(1, 1, MAXV);
    for(int i=0;i<n;i++) {
        int h=arr[i].first, k=arr[i].second;
        int mn=h-k+1;
        int val=query(1, 1, MAXV, mn);
        int i1=fstidx(1, 1, MAXV, val);
        int i2=fstidx(1, 1, MAXV, val-1);
        if(i2<=h) update(1, 1, MAXV, i2, h, 1);
        int cnt=min(i2, h+1)-mn;
        update(1, 1, MAXV, i1, i1+cnt-1, 1);
    }
    int64_t ans=0;
    for(int i=1;i<=MAXV;i++) {
        int64_t cur=query(1, 1, MAXV, i);
        ans+=cur*(cur-1)/2;
    }
    cout << ans << endl;
    return 0;
}

• 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