Submission #235529

#	Time	Username	Problem	Language	Result	Execution time	Memory
235529		nicolaalexandra	Sails (IOI07_sails)	C++14	100 / 100	714 ms	6412 KiB

sails

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

struct segment_tree{
    long long sum,lazy;
} aint[DIM*4];
pair <int,int> v[DIM];
int n,i,maxi;
long long sol;

void update_lazy (int nod, int st, int dr){
    if (!aint[nod].lazy)
        return;
    if (st != dr){
        int fiu_st = nod<<1, fiu_dr = (nod<<1)|1, mid = (st+dr)>>1;
        aint[fiu_st].sum += aint[nod].lazy * (mid-st+1);
        aint[fiu_st].lazy += aint[nod].lazy;

        aint[fiu_dr].sum += aint[nod].lazy * (dr - mid);
        aint[fiu_dr].lazy += aint[nod].lazy;
    }
    aint[nod].lazy = 0;
}
void update (int nod, int st, int dr, int x, int y, int val){
    update_lazy (nod,st,dr);
    if (x <= st && dr <= y){
        aint[nod].sum += dr-st+1;
        aint[nod].lazy += val;
        update_lazy (nod,st,dr);
        return;
    }
    int mid = (st+dr)>>1;
    if (x <= mid)
        update (nod<<1,st,mid,x,y,val);
    if (y > mid)
        update ((nod<<1)|1,mid+1,dr,x,y,val);
    update_lazy (nod<<1,st,mid);
    update_lazy ((nod<<1)|1,mid+1,dr);

    aint[nod].sum = aint[nod<<1].sum + aint[(nod<<1)|1].sum;
}

void query (int nod, int st, int dr, int x, int y){
    update_lazy (nod,st,dr);
    if (x <= st && dr <= y){
        sol += aint[nod].sum;
        return;
    }
    int mid = (st+dr)>>1;
    if (x <= mid)
        query (nod<<1,st,mid,x,y);
    if (y > mid)
        query ((nod<<1)|1,mid+1,dr,x,y);
}

long long get_elem (int nod, int st, int dr, int poz){
    update_lazy (nod,st,dr);
    if (st == dr)
        return aint[nod].sum;
    int mid = (st+dr)>>1;
    if (poz <= mid)
        return get_elem (nod<<1,st,mid,poz);
    else return get_elem ((nod<<1)|1,mid+1,dr,poz);
}
int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n;
    for (i=1;i<=n;i++){
        cin>>v[i].first>>v[i].second;
        maxi = max (maxi,v[i].first);
    }

    sort (v+1,v+n+1);

    for (i=1;i<=n;i++){

        int poz = v[i].first, nr = v[i].second;

        long long val = get_elem (1,1,maxi,poz-nr+1);

        int st = poz-nr+2, dr = poz, sol_poz = maxi + 1;
        while (st <= dr){
            int mid = (st+dr)>>1;
            if (get_elem(1,1,maxi,mid) < val){
                sol_poz = mid;
                dr = mid-1;
            } else st = mid+1;
        }

        if (sol_poz <= poz){

            update (1,1,maxi,sol_poz,poz,1);
            query (1,1,maxi,sol_poz,poz);
            nr -= poz - sol_poz + 1;
        }

        /// cea mai din stanga pozitie egala cu val

        st = 1, dr = poz;
        while (st <= dr){
            int mid = (st+dr)>>1;
            if (get_elem(1,1,maxi,mid) <= val){
                sol_poz = mid;
                dr = mid-1;
            } else st = mid+1;
        }

        update (1,1,maxi,sol_poz,sol_poz+nr-1,1);
        query (1,1,maxi,sol_poz,sol_poz+nr-1);

        sol -= v[i].second;
    }

    cout<<sol;

    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