oj.uz

Submission #235497

# Submission time Handle Problem Language Result Execution time Memory
235497 2020-05-28T11:29:17 Z nicolaalexandra Sails (IOI07_sails) C++14
0 / 100
 747 ms 6400 KB 
#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);
    }

    for (i=n;i;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);

        //cout<<sol - v[i].second<<"\n";
        sol -= v[i].second;
    }

    cout<<sol;

    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 1536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 155 ms 1912 KB Output isn't correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 304 ms 3320 KB Output isn't correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 559 ms 5880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 647 ms 6280 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 747 ms 6400 KB Output isn't correct
2 Halted 0 ms 0 KB -