Submission #784336

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
784336	2023-07-16T03:15:55 Z	1075508020060209tc	New Home (APIO18_new_home)	C++14	10 / 100	4316 ms	67892 KB

new_home

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
int n;
int K;int Q;
int xar[500005];
int typ[500005];
int ta[500005];
int tb[500005];
int qpl[500005];
int qt[500005];
int ansl[500005];int ansr[500005];
int anok[500005];
int kcnt;
int freq[500005];

struct mo{
int l;int r;int id;
};
bool cmp(mo i,mo j){
int va=i.l/500;int vb=j.l/500;
if(va<vb){return 1;}
if(va>vb){return 0;}
if(((va&1)==0)){
    return i.r<j.r;
}
return i.r>j.r;
}

void add(int v){
freq[v]++;
if(freq[v]==1){
    kcnt++;
}
}
void del(int v){
freq[v]--;
if(freq[v]==0){
    kcnt--;
}
}


signed main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin>>n>>K>>Q;
    for(int i=1;i<=n;i++){
        cin>>xar[i]>>typ[i]>>ta[i]>>tb[i];
    }
    for(int i=1;i<=Q;i++){
        cin>>qpl[i]>>qt[i];
        ansl[i]=0;ansr[i]=1e9;
    }
    vector<pair<int,int>>event;
    vector<int>eventp;
    for(int i=1;i<=n;i++){
        event.push_back({xar[i],typ[i]});
        eventp.push_back(xar[i]);
    }
    sort(eventp.begin(),eventp.end());
    sort(event.begin(),event.end());
    for(int ttt=0;ttt<=29;ttt++){
        vector<mo>qry;
        for(int i=1;i<=Q;i++){
            int mi=ansl[i]+(ansr[i]-ansl[i])/2;
            anok[i]=0;
            if(ansl[i]==ansr[i]){anok[i]=1;continue;}
            mo hi;
            hi.id=i;
            hi.l=lower_bound(eventp.begin(),eventp.end(),qpl[i]-mi)-eventp.begin();
            hi.r=upper_bound(eventp.begin(),eventp.end(),qpl[i]+mi)-eventp.begin();
            hi.r--;
            if(hi.l>hi.r){continue;}
            qry.push_back(hi);
        }
        sort(qry.begin(),qry.end(),cmp);
        for(int i=1;i<=K;i++){
            freq[i]=0;
        }
        kcnt=0;
        int lit=0;int rit=0;
        add(event[0].second);
        for(int i=0;i<qry.size();i++){
            while(lit<qry[i].l){del(event[lit++].second);}
            while(rit>qry[i].r){del(event[rit--].second);}
            while(lit>qry[i].l){add(event[--lit].second);}
            while(rit<qry[i].r){add(event[++rit].second);}
            if(kcnt==K){
                anok[qry[i].id]=1;
            }
        }
        for(int i=1;i<=Q;i++){
            int mi=ansl[i]+(ansr[i]-ansl[i])/2;
            if(anok[i]){
                ansr[i]=mi;
            }else{
                ansl[i]=mi+1;
            }
         //   cout<<anok[i]<<" "<<mi<<endl;
        }
    }
    for(int i=1;i<=Q;i++){
        if(ansl[i]>1e8){
            cout<<-1<<endl;
        }else{
            cout<<ansl[i]<<endl;
        }
    }


}

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:87:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<mo>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for(int i=0;i<qry.size();i++){
      |                     ~^~~~~~~~~~~

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Incorrect	1 ms	340 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Incorrect	1 ms	340 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1990 ms	52136 KB	Output is correct
2	Correct	4019 ms	50436 KB	Output is correct
3	Correct	1961 ms	67852 KB	Output is correct
4	Correct	2019 ms	66116 KB	Output is correct
5	Correct	3898 ms	62536 KB	Output is correct
6	Correct	4051 ms	62912 KB	Output is correct
7	Correct	1923 ms	67892 KB	Output is correct
8	Correct	2132 ms	66116 KB	Output is correct
9	Correct	2626 ms	65448 KB	Output is correct
10	Correct	4316 ms	64024 KB	Output is correct
11	Correct	3002 ms	62912 KB	Output is correct
12	Correct	3178 ms	63888 KB	Output is correct