oj.uz

Submission #158484

# Submission time Handle Problem Language Result Execution time Memory
158484 2019-10-17T10:10:43 Z brcode Sails (IOI07_sails) C++14
30 / 100
 288 ms 8128 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 1e5+5;
const long long MAXM = 1e5;
pair<long long,long long> arr[MAXN];
pair<long long,long long> seg[4*MAXN];
long long lazy[4*MAXN];

void push(long long curr,long long l,long long r){
    if(!lazy[curr]){
        return;
    }
    seg[curr].first+=lazy[curr];
    seg[curr].second+=lazy[curr];
    if(l!=r){
        lazy[2*curr]+=lazy[curr];
        lazy[2*curr+1]+=lazy[curr];
    }
    lazy[curr] = 0;
}
long long atpos(long long curr,long long l,long long r,long long pos){
    if(lazy[curr]){
        push(curr,l,r);
    }
    if(l==r){
        return seg[curr].first;
    }
    long long mid = (l+r)/2;
    push(2*curr+1,mid+1,r);
    push(2*curr,l,mid);
    if(pos<=mid){
        return atpos(2*curr,l,mid,pos);
    }else{
        return atpos(2*curr+1,mid+1,r,pos);
    }

}
long long firstpos(long long curr,long long l,long long r,long long val){

    if(lazy[curr]){
        push(curr,l,r);
    }
    if(l==r){
        if(seg[curr].second<=val){
            return l;
        }
        return -1;
    }
    long long mid = (l+r)/2;
    push(2*curr+1,mid+1,r);
    push(2*curr,l,mid);
    if(seg[2*curr].first>=val && seg[2*curr].second<=val){
        return firstpos(2*curr,l,mid,val);
    }else{
        return firstpos(2*curr+1,mid+1,r,val);
    }
}
long long lastpos(long long curr,long long l,long long r,long long val){
    if(lazy[curr]){
        push(curr,l,r);
    }
    if(l==r){
        if(seg[curr].first>=val){
            return l;
        }
        return -1;
    }
    long long mid =(l+r)/2;
    push(2*curr+1,mid+1,r);
    push(2*curr,l,mid);
    if(seg[2*curr+1].first>=val && seg[2*curr+1].second<=val){
        return lastpos(2*curr+1,mid+1,r,val);
    }else{
        return lastpos(2*curr,l,mid,val);
    }
}
void update(long long curr,long long l,long long r,long long tl,long long tr){

    if(l>r){
        return;
    }
    if(lazy[curr]){
        push(curr,l,r);
    }
    if(r<tl||l>tr){
        return;
    }
    if(l>=tl && r<=tr){
        //cout<<l<<" "<<r<<" "<<tl<<" "<<tr<<endl;
        seg[curr].first++;
        seg[curr].second++;
        //cout<<curr<<" "<<seg[curr].first<<endl;
        if(l!=r){
            lazy[2*curr]++;
            lazy[2*curr+1]++;
        }
        return;
    }
    long long mid =(l+r)/2;
    update(2*curr,l,mid,tl,tr);
    update(2*curr+1,mid+1,r,tl,tr);
    seg[curr].first = max(seg[2*curr].first,seg[2*curr+1].first);
    seg[curr].second = min(seg[2*curr].second,seg[2*curr+1].second);
}
int main(){
    long long n;
    cin>>n;
    for(long long i=1;i<=n;i++){
        cin>>arr[i].first>>arr[i].second;
    }
    sort(arr+1,arr+n+1);
    for(long long i=1;i<=n;i++){
        long long h = arr[i].first;
        long long k = arr[i].second;
        long long last = h-k+1;
        long long val = atpos(1,1,MAXM,last);
        //cout<<atpos(1,1,MAXM,1)<<endl;
        //cout<<h<<" "<<k<<" "<<last<<" "<<val<<endl;
        long long l =firstpos(1,1,MAXM,val);
        long long r = lastpos(1,1,MAXM,val);
        //cout<<val<<" "<<l<<" "<<r<<endl;
        //cout<<atpos(1,1,MAXM,1)<<" "<<firstpos(1,1,MAXM,0)<<endl;
        long long remaining = k;
        if(r+1<=h){
            update(1,1,MAXM,r+1,h);
            //cout<<h<<" "<<k<<" "<<r+1<<" "<<h<<endl;
            remaining = k-(h-(r+1)+1);
        }

        if(remaining>0){
          //  cout<<h<<" "<<k<<" "<<l<<" "<<l+remaining-1<<endl;
            update(1,1,MAXM,l,l+remaining-1);
        }
    }
    long long ans = 0;
    for(long long i=1;i<=1e5;i++){
        long long hold =atpos(1,1,MAXN,i);


        ans+=(hold)*(hold-1)/2;
    }
    cout<<ans<<endl;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 460 KB Output is correct
2 Correct 17 ms 504 KB Output is correct

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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

Subtask #11
0 / 10.0

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