#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
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) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5103 ms |
10840 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5103 ms |
10840 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5041 ms |
27808 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5055 ms |
26176 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5103 ms |
10840 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5103 ms |
10840 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
