Submission #49687

#TimeUsernameProblemLanguageResultExecution timeMemory
49687gs13105New Home (APIO18_new_home)C++17
57 / 100
5026 ms346088 KiB
#include <cstdio> #include <cstdlib> #include <cstring> #include <cassert> #include <iostream> #include <algorithm> #include <string> #include <vector> #include <list> #include <stack> #include <queue> #include <deque> #include <set> #include <map> #include <tuple> #include <iterator> using namespace std; const int MAXN = 300000; const int MAXI = 1048576; const int INF = 100000000; int n, k, q, bp; vector<int> com; inline int idx(int x) { return lower_bound(com.begin(), com.end(), x) - com.begin(); } struct eve { int t, x, d; bool operator <(const eve &e) const { return t != e.t ? t < e.t : d > e.d; } }; struct pos { int c, l, lt, r, rt; }; vector<eve> arr; map<int, pos> loc[MAXN + 10]; struct seg { int t1, t2, x, y; bool operator <(const seg &e) const { return x < e.x; } }; vector<seg> sor[2]; inline void add_seg(int t1, int t2, int x, int y) { if(t1 > t2 || x == y) return; int nt1 = bp + idx(t1); int nt2 = bp + idx(t2 + 1) - 1; if(nt1 > nt2) return; if(y < x) sor[0].push_back({ nt1, nt2, y, x }); else sor[1].push_back({ nt1, nt2, INF - y + 1, INF - x + 1 }); } struct ent { // v0 : dec, v1 : inc, q : query // v : { x, y } // q : { x, i } vector<pair<int, int>> v[2]; vector<pair<int, int>> q; }; ent mem[MAXI + 10]; struct que { int l, y, i; bool operator <(const que &x) const { return l < x.l; } }; vector<que> inp; bool chk[MAXN + 10]; int ans[MAXN + 10]; int main() { //freopen("in", "r", stdin); //freopen("out", "w", stdout); scanf("%d%d%d", &n, &k, &q); for(int i = 0; i < n; i++) { int x, t, a, b; scanf("%d%d%d%d", &x, &t, &a, &b); arr.push_back({ a, x, t }); arr.push_back({ b, x, -t }); } for(int i = 0; i < q; i++) { int l, y; scanf("%d%d", &l, &y); inp.push_back({ l, y, i }); com.push_back(y); } sort(com.begin(), com.end()); com.erase(unique(com.begin(), com.end()), com.end()); int sz = (int)com.size(); for(bp = 1; bp < sz; bp *= 2); sort(arr.begin(), arr.end()); int cur, cnt = 0; for(eve &e : arr) { if(e.d > 0) { if(loc[e.d].size() == 0) { cnt++; if(cnt == k) cur = e.t; } auto it = loc[e.d].find(e.x); if(it != loc[e.d].end()) { it->second.c++; continue; } it = loc[e.d].insert({ e.x,{ 1, 1, e.t, INF, e.t } }).first; pos &p = it->second; if(it != loc[e.d].begin()) { int x = prev(it)->first; pos &q = prev(it)->second; add_seg(q.rt, e.t - 1, x, q.r); q.rt = e.t; q.r = (x + e.x) / 2; p.l = (x + e.x + 1) / 2; } if(next(it) != loc[e.d].end()) { int x = next(it)->first; pos &q = next(it)->second; add_seg(q.lt, e.t - 1, x, q.l); q.lt = e.t; q.l = (x + e.x + 1) / 2; p.r = (x + e.x) / 2; } } else { e.d = -e.d; auto it = loc[e.d].find(e.x); pos &p = it->second; if(p.c > 1) { p.c--; continue; } add_seg(p.lt, e.t, e.x, p.l); add_seg(p.rt, e.t, e.x, p.r); if(it != loc[e.d].begin()) { int x = prev(it)->first; pos &q = prev(it)->second; add_seg(q.rt, e.t, x, q.r); q.rt = e.t + 1; if(next(it) != loc[e.d].end()) { int y = next(it)->first; q.r = (x + y) / 2; } else q.r = INF; } if(next(it) != loc[e.d].end()) { int x = next(it)->first; pos &q = next(it)->second; add_seg(q.lt, e.t, x, q.l); q.lt = e.t + 1; if(it != loc[e.d].begin()) { int y = prev(it)->first; q.l = (y + x + 1) / 2; } else q.l = 1; } loc[e.d].erase(it); if(loc[e.d].size() == 0) { if(cnt == k) { int t1 = idx(cur); int t2 = idx(e.t + 1) - 1; for(int i = t1; i <= t2; i++) chk[i] = 1; } cnt--; } } } sort(inp.begin(), inp.end()); for(que &e : inp) { int x = idx(e.y); if(chk[x]) { x += bp; while(x) { mem[x].q.push_back({ e.l, e.i }); x /= 2; } } else ans[e.i] = -1; } for(int i = 0; i < 2; i++) { sort(sor[i].begin(), sor[i].end()); for(seg &e : sor[i]) { int t1 = e.t1; int t2 = e.t2; while(t1 < t2) { if(t1 % 2 == 1) { mem[t1].v[i].push_back({ e.x, e.y }); t1++; } if(t2 % 2 == 0) { mem[t2].v[i].push_back({ e.x, e.y }); t2--; } t1 /= 2; t2 /= 2; } if(t1 == t2) mem[t1].v[i].push_back({ e.x, e.y }); } } for(int x = 1; x <= bp + sz - 1; x++) { { int mx, p1, p2, sz1, sz2; sz1 = (int)mem[x].v[0].size(); sz2 = (int)mem[x].q.size(); mx = p1 = p2 = 0; while(p2 < sz2) { int qx, qi; tie(qx, qi) = mem[x].q[p2]; if(p1 != sz1 && mem[x].v[0][p1].first <= qx) { mx = max(mx, mem[x].v[0][p1].second); p1++; } else { ans[qi] = max(ans[qi], mx - qx); p2++; } } } { int mx, p1, p2, sz1; sz1 = (int)mem[x].v[1].size(); mx = p1 = 0; p2 = (int)mem[x].q.size() - 1; while(p2 >= 0) { int qx, qi; tie(qx, qi) = mem[x].q[p2]; qx = INF - qx + 1; if(p1 != sz1 && mem[x].v[1][p1].first <= qx) { mx = max(mx, mem[x].v[1][p1].second); p1++; } else { ans[qi] = max(ans[qi], mx - qx); p2--; } } } } for(int i = 0; i < q; i++) printf("%d\n", ans[i]); return 0; }

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:104:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &k, &q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:108:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d%d", &x, &t, &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:116:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &l, &y);
         ~~~~~^~~~~~~~~~~~~~~~
#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...