Submission #1258470

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258470		quocbaoo	Sails (IOI07_sails)	C++20	100 / 100	82 ms	3908 KiB

sails

#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std;
const int N=1e5+5;
ll st[N*4+5];pair<ll,ll> a[N+5];
void update(int id,int l,int r,int u,int v){
    if (l>u||r<u) return ;
    if (l==r){
        st[id]+=v;return;
    }
    int mid=(l+r)/2;
    update(id*2,l,mid,u,v);update(id*2+1,mid+1,r,u,v);
    st[id]=min(st[id*2],st[id*2+1]);
}
int lay1(int id,int l,int r,int u,int v){
    if (l>v||r<u) return -1;
    if (st[id]>=0) return -1;
    if (l==r) return l;
    int mid=(l+r)/2;
    int ans=lay1(id*2,l,mid,u,v);if (ans==-1) ans=lay1(id*2+1,mid+1,r,u,v);
    return ans;
}
int lay2(int id,int l,int r,int u,int v){
    if (l>v||r<u) return -1;
    if (st[id]>=0) return -1;
    if (l==r) return l;
    int mid=(l+r)/2;
    int ans=lay2(id*2+1,mid+1,r,u,v);if (ans==-1) ans=lay2(id*2,l,mid,u,v);
    return ans;
}
int get(int id,int l,int r,int u){
    if (l>u||r<u) return 0;
    if (l==r) return st[id];
    int mid=(l+r)/2;
    return get(id*2,l,mid,u)+get(id*2+1,mid+1,r,u);
}
int main(){
    if (fopen("sail.inp","r")){
        freopen("sail.inp","r",stdin);
        freopen("sail.out","w",stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n;cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i].fi>>a[i].se;
    sort(a+1,a+n+1);
    for (int i=1;i<=n;i++){
        int z=lay1(1,1,N,a[i].fi-a[i].se+1,a[i].fi);
        if (z!=-1){
            update(1,1,N,z,1);update(1,1,N,a[i].fi+1,-1);
            a[i].se-=(a[i].fi-z+1);
        }
        else z=a[i].fi+1;
        if (a[i].se>0){
            int z1=lay2(1,1,N,1,z-1);
            if (z1==-1){
                update(1,1,N,1,1);update(1,1,N,a[i].se+1,-1);
            }
            else {
                update(1,1,N,z1,1);update(1,1,N,z1+a[i].se,-1);
            }
        }
    }
    ll s=0,to=0;
    for (int i=1;i<=N;i++){
        s=s+get(1,1,N,i);
//        cout<<s<<" ";
        to+=(s*(s-1)/2);
    }
    cout<<to;
}

Compilation message (stderr)

sails.cpp: In function 'int main()':
sails.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         freopen("sail.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
sails.cpp:42:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         freopen("sail.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• 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