oj.uz

Submission #151244

# Submission time Handle Problem Language Result Execution time Memory
151244 2019-09-02T09:58:51 Z georgerapeanu Sails (IOI07_sails) C++11
30 / 100
 200 ms 3064 KB 
#include <cstdio>
#include <algorithm>

using namespace std;

const int NMAX = 1e5;

int n;
pair<int,int> v[NMAX + 5];

int aint[4 * NMAX + 5];
int lazy[4 * NMAX + 5];

long long ans;

void propag(int nod,int st,int dr){
    if(lazy[nod] == 0 || st == dr){
        return ;
    }
    aint[2 * nod] += lazy[nod];lazy[2 * nod] += lazy[nod];
    aint[2 * nod + 1] += lazy[nod];lazy[2 * nod + 1] += lazy[nod];
    lazy[nod] = 0;
}

void dfs(int nod,int st,int dr){
    propag(nod,st,dr); 
    if(st == dr){
        ans += 1LL * (aint[nod] - 1) * (aint[nod]) / 2;
        return ;
    }

    dfs(nod * 2,st,(st + dr) / 2);
    dfs(nod * 2 + 1,(st + dr) / 2 + 1,dr);
}

void update(int nod,int st,int dr,int l,int r,int val){
    propag(nod,st,dr);
    
    if(l <= st && dr <= r){
        lazy[nod] += val;
        aint[nod] += val;
        return ;
    }
    
    if(r < st || l > dr){
        return ;
    }
    
    update(nod * 2,st,(st + dr) / 2,l,r,val);
    update(nod * 2 + 1,(st + dr) / 2 + 1,dr,l,r,val);

    aint[nod] = min(aint[2 * nod],aint[2 * nod + 1]);
}

int find_pos(int nod,int st,int dr,int val){///leftmost pos with value <= val
    propag(nod,st,dr);
    if(st == dr){
        return st;
    }
    if(aint[2 * nod] <= val){
        return find_pos(2 * nod,st,(st + dr) / 2,val);
    }
    else{
        return find_pos(2 * nod + 1,(st + dr) / 2 + 1,dr,val);
    }
}

int get_val(int nod,int st,int dr,int pos){
    propag(nod,st,dr);
    if(st == dr){
        return aint[nod];
    }
    if(pos <= (st + dr) / 2){
        return get_val(nod * 2,st,(st + dr) / 2,pos);
    }
    else{
        return get_val(nod * 2 + 1,(st + dr) / 2 + 1,dr,pos);
    }
}


int main(){

    scanf("%d",&n);

    for(int i = 1;i <= n;i++){
        scanf("%d %d",&v[i].first,&v[i].second);
    }

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

    for(int i = 1;i <= n;i++){
        int tmp = get_val(1,1,NMAX,v[i].first - v[i].second + 1);
        int l1 = find_pos(1,1,NMAX,tmp);
        int l2 = (tmp == 0 ? v[i].first + 1:find_pos(1,1,NMAX,tmp - 1));

        if(v[i].first - l2 + 1 > 0){
            update(1,1,NMAX,l2,v[i].first,1);
            v[i].second -= (v[i].first - l2 + 1);
        }
        if(v[i].second > 0){
            update(1,1,NMAX,l1,l1 + v[i].second - 1,1);
        }
    }

    dfs(1,1,NMAX + 5);

    printf("%lld\n",ans);

    return 0;
}

Compilation message

sails.cpp: In function 'int main()':
sails.cpp:84:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
sails.cpp:87:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&v[i].first,&v[i].second);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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

Subtask #11
0 / 10.0

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