oj.uz

Submission #784329

# Submission time Handle Problem Language Result Execution time Memory
784329 2023-07-16T03:06:05 Z 1075508020060209tc New Home (APIO18_new_home) C++14
0 / 100
 2442 ms 63948 KB 
#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%2==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<=55;ttt++){
        vector<mo>qry;
        for(int i=1;i<=Q;i++){
            int mi=ansl[i]+(ansr[i]-ansl[i])/2;
            anok[i]=0;
            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){del(event[--lit].second);}
            while(rit<qry[i].r){del(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;
            }
        }
    }
    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:86:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<mo>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |         for(int i=0;i<qry.size();i++){
      |                     ~^~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 35.0

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

Subtask #6
0 / 20.0

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