제출 #445600

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
445600		Deepesson	Examination (JOI19_examination)	C++17	100 / 100	1388 ms	138556 KiB

examination

#include <bits/stdc++.h>
#define SQRTN 320
#define MAX 100005
typedef std::pair<int,int> pii;
int tab[325][325];
int sumed[325][325];
int t(int x,int y) {
    if(x<0||y<0)return 0;
    return sumed[x][y];
}
int subrec(int x1,int y1,int x2,int y2) {
    if(x1==-1||x2==-1||y1==-1||y2==-1)return 0;
    return t(x2,y2)-t(x2,y1-1)-t(x1-1,y2)+t(x1-1,y1-1);
}
void clear(void){memset(&tab[0][0],0,sizeof(tab));}
void comp(void) {
    for(int i = 0; i != 325;++i) {
        int val = 0;
        for(int j = 0; j != 325;++j) {
            val += tab[i][j];
            sumed[i][j]=val;
            if(i)sumed[i][j]+=sumed[i-1][j];
        }
    }
}
pii valores[MAX];
int N,Q;
struct bucket {
    pii valores[SQRTN];
    int l,r;
};
int respostas[MAX][320];
bucket baldes[320];
typedef std::pair<pii,int> ppi;
std::vector<ppi> queries;
std::vector<pii> VA,VB,VC;
int compressao[MAX][3];
void obter_respostas(bucket& ref,int tosave) {
    std::map<int,bool> re1,re2;
    for(int i=0;i!=ref.r-ref.l+1;++i){
        re1[ref.valores[i].first]=true;
        re2[ref.valores[i].second]=true;
    }
    std::map<int,int> fim1,fim2;
    std::vector<int> v1,v2;
    {
        int cur=0;
        for(auto&x:re1) {
            fim1[x.first]=cur;++cur;
            v1.push_back(x.first);
        }
    }
    {
        int cur=0;
        for(auto&x:re2) {
            fim2[x.first]=cur;++cur;
            v2.push_back(x.first);
        }
    }
    for(int i=0;i!=MAX;++i){
        compressao[i][0]=compressao[i][1]=compressao[i][2]=-1;
    }
    int tabela[SQRTN][3];
    clear();
    {
        int cursor=0;
        int cursor2=0;
        for(;;) {
            if(VA[cursor2].first
               <=v1[cursor]){
                compressao[VA[cursor2].second][0]=cursor;++cursor2;
            }else ++cursor;
            if(cursor==v1.size())break;
            if(cursor2==VA.size())break;
        }
    }
    {
        int cursor=0;
        int cursor2=0;
        for(;;) {
            if(VB[cursor2].first<=v2[cursor]){
                compressao[VB[cursor2].second][1]=cursor;++cursor2;
            }else ++cursor;
            if(cursor==v2.size())break;
            if(cursor2==VB.size())break;
        }
    }
    for(int i=0;i!=ref.r-ref.l+1;++i){
        tab[fim1[ref.valores[i].first]][fim2[ref.valores[i].second]]++;
    }
    comp();
    for(int i=0;i!=queries.size();++i) {
        (respostas[i][tosave]=subrec(compressao[i][0],compressao[i][1],322,322));
    }
}
int main()
{
    for(auto&x:baldes)x.r=-1;
    std::cin >> N >> Q;
    for(int i=0;i!=N;++i){
        std::cin>>valores[i].first>>valores[i].second;
    }
    std::sort(valores,&valores[N],[](auto x,auto y){return x.first+x.second<y.first+y.second;});
    for(int i=0;i!=Q;++i) {
        int a,b,c;
        std::cin>>a>>b>>c;
        queries.push_back({{a,b},c});
        VA.push_back({a,i});
        VB.push_back({b,i});
        VC.push_back({c,i});
    }
    std::sort(VA.begin(),VA.end());
    std::sort(VB.begin(),VB.end());
    std::sort(VC.begin(),VC.end());
    int ind=0,count=0;
    for(int i=0;i!=N;++i){
        baldes[ind].valores[count]=valores[i];
        ++count;
        if(count==SQRTN) {
            baldes[ind].r=i;
            ++ind;
            baldes[ind].l=i+1;
            count=0;
        }
    }
    baldes[ind].r=N-1;
    {
        int cur=0;
        for(auto&x:baldes){
            if(x.l>=N)continue;
            if(x.r==-1)break;
            obter_respostas(x,cur);
            ++cur;
        }
    }
    for(int i=0;i!=Q;++i) {
        int count=0;
        int min = queries[i].second;
        for(int j=0;j!=320;++j) {
            auto&x=baldes[j];
            if(x.r==-1)break;
            if(x.l>=N)continue;
            if(x.valores[x.r-x.l].first+x.valores[x.r-x.l].second<min)continue;
            if(x.valores[0].first+x.valores[0].second>=min) {
                count+=respostas[i][j];
            }else {
                for(int k=0;k!=x.r-x.l+1;++k) {
                    if(x.valores[k].first+x.valores[k].second>=min&&
                       x.valores[k].first>=queries[i].first.first&&
                       x.valores[k].second>=queries[i].first.second)++count;
                }
            }
        }
        std::cout<<count<<"\n";
    }
}

컴파일 시 표준 에러 (stderr) 메시지

examination.cpp: In function 'void obter_respostas(bucket&, int)':
examination.cpp:73:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |             if(cursor==v1.size())break;
      |                ~~~~~~^~~~~~~~~~~
examination.cpp:74:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |             if(cursor2==VA.size())break;
      |                ~~~~~~~^~~~~~~~~~~
examination.cpp:84:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |             if(cursor==v2.size())break;
      |                ~~~~~~^~~~~~~~~~~
examination.cpp:85:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |             if(cursor2==VB.size())break;
      |                ~~~~~~~^~~~~~~~~~~
examination.cpp:92:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for(int i=0;i!=queries.size();++i) {
      |                 ~^~~~~~~~~~~~~~~~
examination.cpp:63:9: warning: unused variable 'tabela' [-Wunused-variable]
   63 |     int tabela[SQRTN][3];
      |         ^~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57