Submission #968864

#TimeUsernameProblemLanguageResultExecution timeMemory
968864socpiteNew Home (APIO18_new_home)C++14
57 / 100
5104 ms344544 KiB
// #pragma GCC optimize("arch=skylake") #include<bits/stdc++.h> using namespace std; const int maxn = 4e5+5; const int INF = 1e9+5; vector<pair<int, pair<int, int>>> ev; vector<int> cp, cpy; int n, q, k; int ans[maxn]; int p[maxn], ty[maxn]; int L[maxn], Y[maxn]; int st[4*maxn][2]; struct ev_upd{ int l, r, ty; ev_upd(int _l, int _r, int _ty): l(_l), r(_r), ty(_ty){}; }; vector<pair<int, int>> leaf_q[maxn]; set<pair<int, int>> pos[maxn]; int last_time[maxn][2]; vector<ev_upd> st_time[4*maxn]; int crrt; pair<pair<int, int>, int> undo_stack[maxn*100]; int stksz = 0; // 0 is min, 1 is max void upd_st(ev_upd &ele, int &cnt, int l = 0, int r = cp.size()-1, int id = 1){ if(ele.l > ele.r || ele.l > cp[r] || ele.r < cp[l])return; if(ele.l <= cp[l] && cp[r] <= ele.r){ if(ele.ty == 0){ if(st[id][0] > ele.l){ undo_stack[stksz++] = make_pair(make_pair(id, 0), st[id][0]); st[id][0] = ele.l; cnt++; } } else { if(st[id][1] < ele.r){ undo_stack[stksz++] = make_pair(make_pair(id, 1), st[id][1]); st[id][1] = ele.r; cnt++; } } } else { int mid = (l+r)>>1; upd_st(ele, cnt, l, mid, id<<1); upd_st(ele, cnt, mid+1, r, id<<1|1); } } int query_st(int pos, int l = 0, int r = cp.size()-1, int id = 1){ int re = max(st[id][1] - pos, pos - st[id][0]); if(l < r){ int mid = (l + r)>>1; if(pos <= cp[mid])re = max(re, query_st(pos, l, mid, id<<1)); else re = max(re, query_st(pos, mid+1, r, id<<1|1)); } return re; } void time_add(int ql, int qr, const ev_upd &ele, int l = 0, int r = cpy.size()-1, int id = 1){ // cout << ql << " " << qr << " " << ele.l << " " << ele.r << " " << ele.ty << endl; if(ql > qr || ql > cpy[r] || qr < cpy[l])return; if(ql <= cpy[l] && cpy[r] <= qr)st_time[id].push_back(ele); else { int mid = (l+r)>>1; time_add(ql, qr, ele, l, mid, id<<1); time_add(ql, qr, ele, mid+1, r, id<<1|1); } } int sumcol[maxn]; int sumall = 0, ptr = 0; void time_dfs(int l = 0, int r = cpy.size()-1, int id = 1){ int cnt = 0; for(auto &ele: st_time[id]) { upd_st(ele, cnt); } if(l == r){ while(ptr < ev.size() && ev[ptr].first <= cpy[l]){ if(ev[ptr].second.first){ sumcol[ty[ev[ptr].second.second]]--; if(!sumcol[ty[ev[ptr].second.second]])sumall--; } else { if(!sumcol[ty[ev[ptr].second.second]])sumall++; sumcol[ty[ev[ptr].second.second]]++; } ptr++; } // cout << sumall << endl; for(auto qq: leaf_q[l]){ ans[qq.second] = sumall < k ? -1 : query_st(qq.first); } } else { int mid = (l+r)>>1; time_dfs(l, mid, id<<1); time_dfs(mid+1, r, id<<1|1); } for(int i = 0; i < cnt; i++){ stksz--; st[undo_stack[stksz].first.first][undo_stack[stksz].first.second] = undo_stack[stksz].second; } } void add_range(int l, int r){ if(l != -INF)last_time[l][0] = crrt; if(r != INF)last_time[r][1] = crrt; } void del_range(int l, int r){ // return; if(l == -INF){ ev_upd ele(-INF, p[r], 1); time_add(last_time[r][1], crrt-1, ele); last_time[r][1] = 0; } else if(r == INF){ time_add(last_time[l][0], crrt-1, ev_upd(p[l], INF, 0)); last_time[l][0] = 0; } else { int mid = (p[l]+p[r])/2; time_add(last_time[l][0], crrt-1, ev_upd(p[l], mid, 0)); time_add(last_time[r][1], crrt-1, ev_upd(mid+1, p[r], 1)); last_time[r][1] = 0; last_time[l][0] = 0; } } void add(int x, int col){ // cout << x << endl; auto it = pos[col].insert(make_pair(p[x], x)).first; if(pos[col].size() == 1){ add_range(-INF, x); add_range(x, INF); } else { if(next(it) == pos[col].end()){ int prv = prev(it)->second; del_range(prv, INF); add_range(prv, x); add_range(x, INF); } else if(it == pos[col].begin()){ int nxt = next(it)->second; del_range(-INF, nxt); add_range(-INF, x); add_range(x, nxt); } else { int prv = prev(it)->second; int nxt = next(it)->second; del_range(prv, nxt); add_range(prv, x); add_range(x, nxt); } } } void del(int x, int col){ // cout << "DEL " << x << endl; auto it = pos[col].erase(pos[col].find(make_pair(p[x], x))); if(pos[col].size() == 0){ del_range(-INF, x); del_range(x, INF); } else { if(it == pos[col].end()){ int prv = prev(it)->second; del_range(x, INF); del_range(prv, x); add_range(prv, INF); } else if(it == pos[col].begin()){ int nxt = it->second; del_range(-INF, x); del_range(x, nxt); add_range(-INF, nxt); } else { int prv = prev(it)->second; int nxt = it->second; del_range(x, nxt); del_range(prv, x); add_range(prv, nxt); } } } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> k >> q; for(int i = 0; i < 4*maxn; i++)st[i][0] = INF, st[i][1] = -INF; for(int i = 1; i <= n; i++){ int a, b; cin >> p[i] >> ty[i] >> a >> b; ev.push_back({a, {0, i}}); ev.push_back({b+1, {1, i}}); } for(int i = 1; i <= q; i++){ cin >> L[i] >> Y[i]; cp.push_back(L[i]); cpy.push_back(Y[i]); } sort(cp.begin(), cp.end()); cp.erase(unique(cp.begin(), cp.end()), cp.end()); sort(cpy.begin(), cpy.end()); cpy.erase(unique(cpy.begin(), cpy.end()), cpy.end()); sort(ev.begin(), ev.end()); for(int i = 1; i <= q; i++)leaf_q[lower_bound(cpy.begin(), cpy.end(), Y[i]) - cpy.begin()].push_back({L[i], i}); for(auto v: ev){ crrt = v.first; if(v.second.first)del(v.second.second, ty[v.second.second]); else add(v.second.second, ty[v.second.second]); } // cout << "SUS" << endl; // if(n > 100000)return 0; time_dfs(); for(int i = 1; i <= q; i++)cout << ans[i] << "\n"; }

Compilation message (stderr)

new_home.cpp: In function 'void time_dfs(int, int, int)':
new_home.cpp:92:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         while(ptr < ev.size() && ev[ptr].first <= cpy[l]){
      |               ~~~~^~~~~~~~~~~
#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...