Submission #1196195

#TimeUsernameProblemLanguageResultExecution timeMemory
1196195countlessNew Home (APIO18_new_home)C++20
5 / 100
5038 ms1114112 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; const ll MOD = 998244353; const ll INF = 1e18; const ld EPS = 1e-12; #define endl "\n" #define sp <<" "<< #define REP(i, a, b) for(ll i = a; i < b; i++) #define dbg(x) cout << #x << " = " << x << endl #define mp make_pair #define pb push_back #define fi first #define se second #define fast_io() ios_base::sync_with_stdio(false); cin.tie(NULL) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define sz(x) ((ll)(x).size()) struct custom_hash { static uint64_t splitmix64(uint64_t x) { // http://xorshift.di.unimi.it/splitmix64.c x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } }; template <typename Key, typename Value> using hash_map = unordered_map<Key, Value, custom_hash>; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); // uniform_int_distribution<int>(a, b)(rng); // shuffle(all(a), rng); struct store { int loc, type, start, end; store(int loc = -1, int type = -1, int start = -1, int end = -1) : loc(loc), type(type), start(start), end(end) {;;} bool operator<(const store &other) const { return end < other.end; } }; struct query { int loc, year, ind; query(int loc = -1, int year = -1, int ind = -1) : loc(loc), year(year), ind(ind) {;;} bool operator<(const query &other) const { return year < other.year; } }; bool compS(const store &a, const store &b) { return a.start < b.start; } bool compQ(const query &a, const query &b) { return a.year < b.year; } void solution() { int n, k, q; cin >> n >> k >> q; vector<store> stores(n); REP(i, 0, n) { cin >> stores[i].loc >> stores[i].type >> stores[i].start >> stores[i].end; } vector<unordered_map<int, int>> ans(q); vector<query> queries(q); REP(i, 0, q) { cin >> queries[i].loc >> queries[i].year; queries[i].ind = i; } sort(all(queries), compQ); for (auto &x : stores) { int st = lower_bound(all(queries), query(int(1e8+1), x.start)) - queries.begin(); int en = upper_bound(all(queries), query(int(1e8+1), x.end)) - queries.begin(); while (st != en) { int in = queries[st].ind; if (ans[in].count(x.type) == 0) { ans[in][x.type] = abs(queries[st].loc - x.loc); } else { ans[in][x.type] = min(ans[in][x.type], abs(queries[st].loc - x.loc)); } st++; } } REP(i, 0, q) { if (ans[i].size() == k) { int res = 0; for (auto &x : ans[i]) { res = max(res, x.second); } cout << res << endl; } else { cout << -1 << endl; } } return; } signed main() { fast_io(); solution(); return 0; } // Notes // is it binsearchable? // is it greedy? // is it DP? // if online round: search OEIS, similar topics // put observations together // check for edge cases // try "dumb" solutions, you're fast enough to rewrite // clean up the implementation // keep it simple // check for overflow // check for small N // check for array with same or monotonic a_i
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...