Submission #959514

#	Time	Username	Problem	Language	Result	Execution time	Memory
959514		Hugo1729	Sails (IOI07_sails)	C++11	100 / 100	297 ms	10564 KiB

sails

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define f first
#define s second

int sz=1,n;
vector<ll> t1, lazy1, t2, lazy2;
ll ans=0;

void push1(int v){
    t1[v*2]+=lazy1[v];
    lazy1[v*2]+=lazy1[v];
    t1[v*2+1]+=lazy1[v];
    lazy1[v*2+1]+=lazy1[v];
    lazy1[v]=0;
}

void push2(int v,int width){
    width>>=1;
    t2[v*2]+=lazy2[v]*width;
    lazy2[v*2]+=lazy2[v];
    t2[v*2+1]+=lazy2[v]*width;
    lazy2[v*2+1]+=lazy2[v];
    lazy2[v]=0;
}

void update1(int v, int tl, int tr, int l, int r, int val){
    if(l>r)return;
    if(tl==l&&tr==r){
        t1[v]+=val;
        lazy1[v]+=val;
        return;
    }
    push1(v);
    int mid=(tl+tr)/2;
    update1(2*v,tl,mid,l,min(mid,r),val);
    update1(2*v+1,mid+1,tr,max(mid+1,l),r,val);
    t1[v]=min(t1[v*2],t1[v*2+1]);
}

void update2(int v, int tl, int tr, int l, int r, int val){
    if(l>r)return;
    if(tl==l&&tr==r){
        t2[v]+=val*(tr-tl+1);
        lazy2[v]+=val;
        return;
    }
    push2(v,tr-tl+1);
    int mid=(tl+tr)/2;
    update2(2*v,tl,mid,l,min(mid,r),val);
    update2(2*v+1,mid+1,tr,max(mid+1,l),r,val);
    t2[v]=t2[v*2]+t2[v*2+1];
}

void update(int v, int tl, int tr, int l, int r, int val){
    update1(v, tl, tr, l, r, val);
    update2(v, tl, tr, l, r, val);
}

ll query1(int v, int tl, int tr, int l, int r){
    if(l>r)return 1000001;
    if(tl==l&&tr==r){
        return t1[v];
    }
    push1(v);
    int mid=(tl+tr)/2;
    return min(query1(2*v,tl,mid,l,min(mid,r)),
    query1(2*v+1,mid+1,tr,max(mid+1,l),r));
}
    

ll query2(int v, int tl, int tr, int l, int r){
    if(l>r)return 0;
    if(tl==l&&tr==r){
        return t2[v];
    }
    push2(v,tr-tl+1);
    int mid=(tl+tr)/2;
    return query2(2*v,tl,mid,l,min(mid,r))+
    query2(2*v+1,mid+1,tr,max(mid+1,l),r);
}

int find1(int k){
    int v=1;

    while(v<sz){
        push1(v);
        // cout << v << ' ' << t1[v]<< ' ' << k << '\n';
        if(t1[v*2]<=k)v<<=1;
        else v=v*2+1;
    }

    return v-sz+1;
}

void pushall2(int v, int tl, int tr){
    if(tr>tl){
        // cout << v << ' ' << tr-tl+1 << '\n';
        push2(v,tr-tl+1);
        int mid=(tl+tr)/2;
        pushall2(v*2,tl,mid);
        pushall2(2*v+1,mid+1,tr);
    }
}

int main(){
    // cin.tie(0)->sync_with_stdio(0);
    cin >> n;

    vector<pair<int,int>> flags(n);
    for(int i=0;i<n;i++){
        cin >> flags[i].f >> flags[i].s;
    }

    sort(flags.begin(),flags.end());

    while(sz<flags[n-1].f+1)sz<<=1;
    // sz<<=1;

    t1.assign(2*sz+5,1000001);
    lazy1.assign(2*sz+5,0);

    t2.assign(2*sz+5,0);
    lazy2.assign(2*sz+5,0);

    int sus=1;

    for(int i=0;i<n;i++){
        int h=flags[i].f,k=flags[i].s;

        update1(1,1,sz,sus,h,-1000001);
        sus=h+1;

        // for(int i=1;i<sz*2;i++)cout << i << ' ' << t1[i] << ' ' << lazy1[i] << '\n';

        // for(int i=1;i<sz;i++)push1(i);
        // pushall2(1,1,sz);
        // for(int i=1;i<sz*2;i++)cout << t1[i] << ' ';
        // cout << '\n';
        // for(int i=1;i<sz*2;i++)cout << t2[i] << ' ';
        // cout << '\n';

        int index=find1(query1(1,1,sz,h-k+1,h-k+1));
        int next = min(find1(query1(1,1,sz,h-k+1,h-k+1)-1),h+1);

        // cout << h << ' ' << k << ' ' << index << ' ' << next << '\n';

        ans+=query2(1,1,sz,h-k+1,h);
        // cout << "a";

        update(1,1,sz,index,h,1);
        // cout << "a";
        update(1,1,sz,next-1-(h-k+1)+index+1,next-1,-1);
        // cout << "a";
        // update(1,1,sz,1,k,1);

        // index=find();
        // cout << 'b' <<(k)*(t[index+sz-1]) <<' ' << index << '\n';
        // ans+=(k)*(t[index+sz-1]);
        // update(1,1,sz,index,index+k-1,1);
        // for(int i=1;i<sz;i++)push1(i);
        // pushall2(1,1,sz);
        // for(int i=1;i<sz*2;i++)cout << t1[i] << ' ';
        // cout << '\n';
        // for(int i=1;i<sz*2;i++)cout << t2[i] << ' ';
        // cout << '\n';
    }

    cout << ans;

    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