Submission #936585

#	Time	Username	Problem	Language	Result	Execution time	Memory
936585		heavylightdecomp	New Home (APIO18_new_home)	C++14	0 / 100	5103 ms	27808 KiB

new_home

#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define X first
#define Y second
using pii = pair<int,int>;
#define vt vector
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define f0r(i,a,b) for(auto i = (a); i != (b); i++)
#define r0f(i,a,b) for(auto i = (a); i >= (b); i--)
//sim dor ris eni(x) rge range dud debug 2eni 2dor imie
#define sim template<class c
#define dor > debug& operator<<
#define ris return *this
#define eni(x) sim> typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i)
sim> struct rge { c b,e; };
sim> rge<c> range(c i, c j) { return rge<c>{i,j}; }
sim> auto dud(c* x)->decltype(cout<<*x,0);
sim> char dud(...);
#define cerr while(0) cerr
struct debug {
    ~debug() { cerr << endl; }
    eni(!=) { cerr << boolalpha << i; ris; }
    eni(==) { ris << range(all(i)); }
    sim, class b dor(pair<b,c> d) {
        ris << "(" << d.X << ", " << d.Y << ")";
    }
    sim dor(rge<c> d) {
        *this << "{";
        f0r(it,d.b,d.e) *this << ", " + 2*(it==d.b) << *it;
        ris << "}";
    }
};
#define imie(r...) " [" << #r << ": " << (r) << "] "
const int INF = 1e9, maxn = 3e5+5;
//store vectors of stores of the same type
//solve each type independently by a function that returns a vector
//then max the answer vectors
//if INF output -1
//solve function is basically sweep on the time ranges {l,r} {-1, x} encoding method
//use a set to denote positions of active stores
//1 indexing
int n,k,q;
vt<tuple<int,int,int>> stores[maxn]; //{pos, time_l, time_r}
pii queries[maxn];
int ans[maxn];
void solve(int type) { //BUG: multiset issues
    multiset<int> active;
    auto miss = [&](int p) {
        int res = INF;
        auto lb = active.lower_bound(p);
        if(lb != active.end()) {
            res = min(res, *lb - p);
        }
        if(lb != active.begin()) {
            res = min(res, p - *prev(lb));
        }
        return res;
    };
    //{time, 0/1/2, ref}
    //delete must be 0, insert must be 1, query = 2
    //inc excl ranges
    vt<tuple<int,int,int>> sweep;
    f0r(g,0,sz(stores[type])) {
        auto [pos, l, r] = stores[type][g];
        sweep.pb({r, 0, g});
        sweep.pb({l, 1, g});
    }
    f0r(i,1,q+1) {
        auto [l, y] = queries[i];
        sweep.pb({y, 2, i});
    }
    sort(all(sweep));
    for(auto [t, hmm, ref] : sweep) {
        if(hmm == 0) {
            active.erase(active.find(get<0>(stores[type][ref])));
        } else if(hmm == 1) {
            active.insert(get<0>(stores[type][ref]));
        } else {
            int lol = miss(queries[ref].X);
            ans[ref] = max(ans[ref], lol);
        }
    }
}
signed main() {
    // vt<pii> wow = {{1,2}};
    // debug() << imie(wow);
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> k >> q;
    f0r(i,0,maxn) ans[i] = -INF;
    f0r(i,1,n+1) {
        int x,t,a,b; cin >>x>>t>>a>>b;
        stores[t].pb({x,a,b});
    }
    f0r(i,1,q+1) {
        cin >> queries[i].X >> queries[i].Y;
    }
    f0r(i,1,k+1) {
        solve(i);
    }
    f0r(i,1,q+1) {
        if(ans[i] == INF) {
            cout << -1 << '\n';
        } else {
            cout << ans[i] << '\n';
        }
    }
}

Compilation message (stderr)

new_home.cpp: In function 'void solve(int)':
new_home.cpp:68:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   68 |         auto [pos, l, r] = stores[type][g];
      |              ^
new_home.cpp:73:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   73 |         auto [l, y] = queries[i];
      |              ^
new_home.cpp:77:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   77 |     for(auto [t, hmm, ref] : sweep) {
      |              ^

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