Submission #1276244

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276244		efeg	Sails (IOI07_sails)	C++20	100 / 100	354 ms	8272 KiB

sails

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

#define F first
#define S second
#define all(v) v.begin(),v.end()
#define endl '\n'
#define int long long

typedef pair<int,int> ii; 
typedef vector<int> vi; 
typedef vector<ii> vii; 

struct SegTree{
    int n; vi tree,lazy;
    SegTree(int n) : n(n){
        tree.assign(4 * n + 100,0); 
        lazy.assign(4 * n + 100,0); 
    } 

    void push(int node,int s,int e){
        if (!lazy[node]) return; 
        tree[node] += lazy[node]; 
        if (s != e){
            lazy[node*2] += lazy[node]; 
            lazy[node*2+1] += lazy[node]; 
        }
        lazy[node] = 0; 
    }

    void update(int node,int s,int e,int l,int r){
        push(node,s,e); 
        if (s > e || r < s || e < l) return;
        if (l <= s && e <= r){
            lazy[node]++; 
            push(node,s,e); 
            return; 
        }
        int m = (s+e) / 2; 
        update(node*2,s,m,l,r); 
        update(node*2+1,m+1,e,l,r); 
    }

    int query(int node,int s,int e,int i){
        push(node,s,e); 
        if (s > e || e < i || i < s) return 0; 
        if (s == e && s == i) return tree[node]; 
        int m = (s+e) / 2; 
        if (m < i) return query(node*2+1,m+1,e,i); 
        else return query(node*2,s,m,i); 
    }

    void update(int l,int r) {return update(1,0,n-1,l,r); }
    int query(int i){return query(1,0,n-1,i);}
    int find(int val,int h){
        int s = 0,e = h-1,ans = -1;
        while (s <= e){
            int m = (s+e) / 2; 
            if (query(m) >= val){
                ans = m; 
                s = m+1; 
            } 
            else e = m-1;   
        }
        return ans; 
    }
}; 

int n; 
vii mast; 

int32_t main(){
    ios_base::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL); 
    cin >> n; 
    mast.assign(n,{}); 
    SegTree tree(1e5); 

    for (int i = 0; i < n; i++) cin >> mast[i].F >> mast[i].S; 
    sort(all(mast)); 

    for (int i = 0; i < n; i++){
        int h,k; tie(h,k) = mast[i]; 
        int val = tree.query(h - k); 
        int upd1 = tree.find(val,h);
        int l = tree.find(val+1,h); 
        
        if (upd1+1 < h) {
            tree.update(upd1+1,h-1); 
            tree.update(l+1,l + k - h + upd1 + 1);
        }
        else tree.update(l+1,l + k); 
    }

    int ans = 0; 
    for (int i = 0; i < 1e5; i++){
        int v = tree.query(i); 
        ans += v * (v-1) / 2; 
    }

    cout << ans << endl; 
}

• 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