Submission #1281007

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281007		lambd47	Sails (IOI07_sails)	C++20	100 / 100	146 ms	6808 KiB

sails

#include <bits/stdc++.h>

#define int long long
using namespace std;

#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)

std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());

const int MX=1e5+7;
int seg[4*MX];
int lz[4*MX];

void refresh(int pos, int ini, int fim){
    if(lz[pos]==0)return;
    if(ini==fim){
        seg[pos]+=lz[pos];
        lz[pos]=0;
        return;
    }
    seg[pos]+=lz[pos];
    lz[2*pos]+=lz[pos];
    lz[2*pos+1]+=lz[pos];
    lz[pos]=0;
    return;
}

int get(int pos, int ini, int fim, int id){
    refresh(pos,ini,fim);
    if(ini==fim)return seg[pos];
    int m=(ini+fim)/2;
    if(m>=id){
        return get(2*pos,ini,m,id);
    }
    else{
        return get(2*pos+1,m+1,fim,id);
    }
}

int bb(int pos, int ini, int fim, int val){//mais a esquerda <= val
    refresh(pos,ini,fim);
    if(ini==fim)return ini;
    if(seg[pos]>val)return -1;
    int e=2*pos,d=2*pos+1;
    int m=(ini+fim)/2;
    refresh(e,ini,m);
    refresh(d,m+1,fim);
    if(seg[2*pos]<=val)return bb(2*pos,ini,m,val);
    else return bb(2*pos+1,m+1,fim,val);
}
/*
int bbh(int pos, int ini, int fim, int val){//mais a direita>val
    refresh(pos,ini,fim);
    if(ini==fim)return ini;
    int e=2*pos,d=2*pos+1;
    int m=(ini+fim)/2;
    refresh(e,ini,m);
    refresh(d,m+1,fim);
    if(seg[2*pos]>=val)return bb(2*pos+1,m+1,fim,val);
    else return bb(2*pos,ini,m,val);

}
*/
void upd(int pos, int ini, int fim, int l, int r){
    refresh(pos,ini,fim);
    if(ini>r || fim<l)return;
    if(l<=ini && fim<=r){
        lz[pos]++;
        refresh(pos,ini,fim);
        return;
    }
    int m=(ini+fim)/2;

    upd(2*pos,ini,m,l,r);
    upd(2*pos+1,m+1,fim,l,r);
    seg[pos]=min(seg[2*pos],seg[2*pos+1]);
}


void solve() {
    int n;cin>>n;
    vector<int> h(n);
    vector<int> k(n);
    L(i,0,n-1){
        cin>>h[i]>>k[i];
    }
    
    vector<int> ord(n);
    iota(all(ord),0);
    sort(all(ord),[&](int i, int j){
            return h[i]<h[j];
            });

    const int N=1e5+7;

    for(auto id:ord){
        int hat=get(1,1,N,h[id]-k[id]+1);
        int ate=bb(1,1,N,hat-1);
        int d=h[id]-ate+1;
        if(ate==-1){
            d=0;
        }
        else{
            upd(1,1,N,ate,h[id]);
        }
        if(d!=k[id]){
            ate=bb(1,1,N,hat);
            upd(1,1,N,ate,ate+k[id]-d-1);
        }
        //cout<<"\n";
    }
    int resp=0;
    L(i,1,h[ord[n-1]]){
        int x=get(1,1,N,i);
    //    cout<<x<<" ";
        resp+=((x*(x-1))/2);
    }
    cout<<resp<<"\n";

}
 
int32_t main() {
    std::cin.tie(0)->sync_with_stdio(0); 
    std::cin.exceptions(std::cin.failbit);

    int T = 1;
//    std::cin >> T;
    while(T--) {
        solve();
    }

	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