Submission #480695

#	Time	Username	Problem	Language	Result	Execution time	Memory
480695		Deepesson	Sails (IOI07_sails)	C++17	0 / 100	154 ms	3940 KiB

sails

#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 (stderr)

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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 5
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10