oj.uz

Submission #235529

# Submission time Handle Problem Language Result Execution time Memory
235529 2020-05-28T12:37:56 Z nicolaalexandra Sails (IOI07_sails) C++14
100 / 100
 714 ms 6412 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);
    }

    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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 512 KB Output is correct
2 Correct 13 ms 4480 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 1528 KB Output is correct
2 Correct 136 ms 1016 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 1912 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 3372 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 571 ms 5996 KB Output is correct
2 Correct 485 ms 5880 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 603 ms 6272 KB Output is correct
2 Correct 267 ms 6008 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 714 ms 6412 KB Output is correct
2 Correct 452 ms 3192 KB Output is correct