Submission #946082

#	Time	Username	Problem	Language	Result	Execution time	Memory
946082		beepbeepsheep	New Home (APIO18_new_home)	C++17	0 / 100	5115 ms	891152 KiB

new_home

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<ll,ll>
#define iii tuple<ll,ll,ll>

#ifndef DEBUG
#define cerr if (0) cerr
#define endl '\n'
#endif // DEBUG

const ll maxn=2e5+5;
const ll inf=1e15;
const ll mod=1e9+7;

vector<tuple<ll,ll,ll>> v;
vector<tuple<ll,ll,ll>> q; //position, l, r
vector<ll> pos;
struct node{
    ll s,e,m,val;
    node *l,*r;
    node (ll _s, ll _e){
        s=_s,e=_e,m=(s+e)>>1,val=0;
        if (s!=e) l=new node(s,m),r=new node(m+1,e);
    }
    void upd(ll x, ll v){
        if (s==e){
            val+=v;
            return;
        }
        if (x>m) r->upd(x,v);
        else l->upd(x,v);
        val=l->val+r->val;
    }
    ll query(ll x, ll y){
        if (x<=s && e<=y) return val;
        if (x>m) return r->query(x,y);
        if (y<=m) return l->query(x,y);
        return l->query(x,y)+r->query(x,y);
    }
}*root;
ll n,k;
void solve(){
    vector<tuple<ll,ll,ll,ll>> q2;
    //l, position, r, idx
    root=new node(0,n);
    for (int i=0;i<q.size();i++){
        ll b,c,d;
        tie(b,c,d)=q[i];
        if (c==d-1) return;
        ll m=(c+d)>>1;
        ll lb=lower_bound(pos.begin(),pos.end(),b-m)-pos.begin();
        ll ub=upper_bound(pos.begin(),pos.end(),b+m)-pos.begin()-1;
        q2.emplace_back(ub,lb,i,m);
    }
    sort(q2.begin(),q2.end());
    //sort by increasing right endpoint, query towards left
    ll ptr=0;
    for (auto [ub,lb,i,m]:q2){
        while (ptr!=v.size() && get<0>(v[ptr])<=ub){
            root->upd(get<1>(v[ptr]),get<2>(v[ptr]));
            ptr++;
        }
        ll a,b,c;
        tie(a,b,c)=q[i];
        ll res=root->query(lb,ub);
        if (res==k) q[i]={a,b,m};
        else q[i]={a,m,c};
    }
}
map<ll,vector<ll>> m;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll qu,x,t,a,b;
    cin>>n>>k>>qu;
    for (int i=1;i<=n;i++){
        cin>>x>>t>>a>>b;
        pos.emplace_back(x);
        m[t].emplace_back(x);
    }
    sort(pos.begin(),pos.end());
    pos.erase(unique(pos.begin(),pos.end()),pos.end());
    for (auto [u,v1]:m){
        sort(v1.begin(),v1.end());
        for (int i=0;i<v1.size();i++){
            v1[i]=lower_bound(pos.begin(),pos.end(),v1[i])-pos.begin();
            if (i!=0){
                v.emplace_back(v1[i],v1[i-1],-1);
                //erase prev
            }
            v.emplace_back(v1[i],v1[i],1);
            //new guy
        }
    }
    sort(v.begin(),v.end());
    for (int i=1;i<=qu;i++){
        cin>>x>>t;
        q.emplace_back(x,-1,100'000'000); //r is can
    }
    for (int i=1;i<=26;i++){
        solve();
    }
    for (auto u:q){
        ll res=get<2>(u);
        if (res>100'000'000) cout<<-1<<'\n';
        else cout<<res<<'\n';
    }
    return 0;
}

Compilation message (stderr)

new_home.cpp: In function 'void solve()':
new_home.cpp:48:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for (int i=0;i<q.size();i++){
      |                  ~^~~~~~~~~
new_home.cpp:61:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::tuple<long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         while (ptr!=v.size() && get<0>(v[ptr])<=ub){
      |                ~~~^~~~~~~~~~
new_home.cpp: In function 'int main()':
new_home.cpp:87:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for (int i=0;i<v1.size();i++){
      |                      ~^~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20