oj.uz

Submission #480695

# Submission time Handle Problem Language Result Execution time Memory
480695 2021-10-17T20:40:19 Z Deepesson Sails (IOI07_sails) C++17
0 / 100
 154 ms 3940 KB 
#include <bits/stdc++.h>
#define MAX 205000
#define LSB(A) (A & (-A))
typedef std::pair<int,int> pii;
int seq[MAX],ft[MAX];
void update(int k,int t){
    while(k<MAX){
        ft[k]+=t;
        k+=LSB(k);
    }
}
int query(int k){
    int res=0;
    while(k>0){
        res+=ft[k];
        k-=LSB(k);
    }
    return res;
}
void update_range(int l,int r,int t){
    update(l,t);
    update(r+1,-t);
}
void clean(){
    memset(ft,0,sizeof(ft));
}
std::vector<pii> vec;
const int base = 150000;
bool solve(int M){
    int cur=0;
    for(int i=0;i!=vec.size();++i){
        int inicio = base-vec[i].first;
        cur=std::max(cur,inicio);
        while(query(cur)==M){
            ++cur;
        }
        int fim = cur+vec[i].second-1;
        if(fim>base)return false;
        update_range(cur,fim,1);
    }
    return true;
}
int main()
{
    for(int i=1;i!=MAX;++i){
        seq[i]=i+seq[i-1];
    }
    int N;
    std::cin>>N;
    for(int i=0;i!=N;++i){
        int H,K;
        std::cin>>H>>K;
        vec.push_back({H,K});
    }
    std::sort(vec.begin(),vec.end());
    std::reverse(vec.begin(),vec.end());
    {
        int l=1,r=MAX;
        while(l<r){
            int m = (l+r)/2;
            clean();
            if(solve(m)){
                r=m;
            }else l=m+1;
        }
        clean();
        solve(l);
    }
    int val=0;
    for(int i=0;i!=MAX;++i){
        int u = query(i);
        if(u>=1){
           // printf("%d ",u);
            val+=seq[query(i)-1];
        }
    }
   // printf("\n");
    std::cout<<val<<"\n";
}

Compilation message

sails.cpp: In function 'bool solve(int)':
sails.cpp:31:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(int i=0;i!=vec.size();++i){
      |                 ~^~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1868 KB Output is correct
2 Incorrect 4 ms 1868 KB Output isn't correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1876 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 1868 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 1868 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 2100 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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

Subtask #11
0 / 10.0

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