Submission #742343

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
742343	2023-05-16T06:48:17 Z	victor_gao	New Home (APIO18_new_home)	C++17	10 / 100	393 ms	62668 KB

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

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.0

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

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	14420 KB	Output is correct
2	Incorrect	8 ms	14380 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	377 ms	55432 KB	Output is correct
2	Correct	343 ms	55340 KB	Output is correct
3	Correct	369 ms	59252 KB	Output is correct
4	Correct	368 ms	57440 KB	Output is correct
5	Correct	354 ms	62668 KB	Output is correct
6	Correct	356 ms	56244 KB	Output is correct
7	Correct	393 ms	59236 KB	Output is correct
8	Correct	366 ms	57360 KB	Output is correct
9	Correct	360 ms	56756 KB	Output is correct
10	Correct	354 ms	55452 KB	Output is correct
11	Correct	299 ms	54604 KB	Output is correct
12	Correct	282 ms	55188 KB	Output is correct