Submission #742343

#	Time	Username	Problem	Language	Result	Execution time	Memory
742343		victor_gao	New Home (APIO18_new_home)	C++17	10 / 100	393 ms	62668 KiB

new_home

//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define N 600015
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
int n,k,q,x[N],t[N],l[N],ans[N];
int vis[N],no;
struct lisan{
    vector<int>vt;
    void in(int x){ vt.push_back(x); }
    void build(){
        sort(vt.begin(),vt.end());
        vt.resize(unique(vt.begin(),vt.end())-vt.begin());
    }
    int idx(int x){ return upper_bound(vt.begin(),vt.end(),x)-vt.begin(); }
    int val(int x){ return vt[x-1]; }
}uni;
vector<int>all[N];
vector<pii>qry;
vector<pii>ok;
int count(pii a,int x){
    return max(abs(a.x-x),abs(a.y-x));
}
signed main(){
    fast
    cin>>n>>k>>q; no=k;
    for (int i=1;i<=n;i++){
        int a,b;
        cin>>x[i]>>t[i]>>a>>b;
        uni.in(x[i]);
    }
    for (int i=1;i<=q;i++){
        int tmp; cin>>l[i]>>tmp;
        qry.push_back({l[i],i});
    }
    sort(qry.begin(),qry.end());
    uni.build();
    for (int i=1;i<=n;i++)
        all[uni.idx(x[i])].push_back(t[i]);
    
    int l=1;
    for (int i=1;i<=uni.vt.size();i++){
        for (auto j:all[i]){
            if (!vis[j]) no--;
            vis[j]++;
        }
        if (no>0) continue;
        while (no==0){
            for (auto j:all[l]){
                if (vis[j]==1) no++;
                vis[j]--;
            }
            l++;
        }
        ok.push_back({uni.val(l-1),uni.val(i)});
    }
    int j=0;
    for (auto [p,i]:qry){
        if (ok.empty()){
            ans[i]=-1;
            continue;
        }
        while (j<(int)(ok.size())-1&&count(ok[j],p)>=count(ok[j+1],p))
            j++;
        ans[i]=count(ok[j],p);
    }
    for (int i=1;i<=q;i++)
        cout<<ans[i]<<"\n";
}

Compilation message (stderr)

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

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