제출 #232935

#제출 시각아이디문제언어결과실행 시간메모리
232935nvmdavaNew Home (APIO18_new_home)C++17
0 / 100
1116 ms127896 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define ff first #define ss second mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define N 1000005 const ll MOD = 1000000007; const int INF = 0x3f3f3f3f; int x[N], ans[N], y[N], l[N], t[N], a[N], b[N]; int n, k, q; vector<int> tmp; vector<pair<int, int> > sh[N]; multiset<pair<int, int> > in; vector<pair<pair<int, int>, pair<int, int> > > lol; int seg[N]; void update(int id, int l, int r, int L, int R, int v){ if(l >= L && r <= R){ seg[id] = max(seg[id], v); return; } if(l > R || r < L) return; int m = (l + r) >> 1; update(id << 1, l, m, L, R, v); update(id << 1 | 1, m + 1, r, L, R, v); } int query(int id, int l, int r, int x){ if(x < l || x > r) return 0; if(l == r) return seg[id]; int m = (l + r) >> 1; return max(seg[id], max(query(id << 1, l, m, x), query(id << 1 | 1, m + 1, r, x))); } void solve(){ lol.clear(); memset(seg, 0, sizeof seg); for(int i = 1; i <= k; ++i){ in.clear(); in.insert({INF, 1}); in.insert({-INF, 1}); for(auto& x : sh[i]){ if(x.ss > 0){ auto r = in.insert({x.ss, x.ff}); auto l = r++; auto it = l--; lol.push_back({{(r -> ff + l -> ff) / 2, r -> ff}, {r -> ss, x.ff - 1}}); in.insert({r -> ff, x.ff}); in.erase(r); } else { auto r = in.lower_bound({x.ss, 0}); auto l = r++; auto it = l--; lol.push_back({{(it -> ff + l -> ff) / 2, it -> ff}, {it -> ss, x.ff - 1}}); lol.push_back({{(it -> ff + r -> ff) / 2, r -> ff}, {r -> ss, x.ff - 1}}); in.insert({r -> ff, x.ff}); in.erase(it); in.erase(r); } } auto r = in.begin(); auto l = r++; lol.push_back({{(r -> ff + l -> ff) / 2, r -> ff}, {r -> ss, tmp.size()}}); } for(int i = 1; i <= q; ++i) lol.push_back({{l[i], 1000000000}, {i, y[i]}}); sort(lol.begin(), lol.end()); for(auto& x : lol){ if(x.ff.ss != 1000000000){ if(x.ss.ff <= x.ss.ss && x.ff.ss > 0){ update(1, 1, 300005, x.ss.ff, x.ss.ss, x.ff.ss); } } else ans[x.ss.ff] = max(ans[x.ss.ff], query(1, 1, 300005, x.ss.ss) - x.ff.ff); } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>k>>q; for(int i = 1; i <= n; ++i) cin>>x[i]>>t[i]>>a[i]>>b[i]; for(int i = 1; i <= q; ++i){ cin>>l[i]>>y[i]; l[i] <<= 1; tmp.push_back(y[i]); } sort(tmp.begin(), tmp.end()); tmp.resize(unique(tmp.begin(), tmp.end()) - tmp.begin()); for(int i = 1; i <= q; ++i) y[i] = upper_bound(tmp.begin(), tmp.end(), y[i]) - tmp.begin(); for(int i = 1; i <= n; ++i){ a[i] = lower_bound(tmp.begin(), tmp.end(), a[i]) - tmp.begin() + 1; b[i] = lower_bound(tmp.begin(), tmp.end(), b[i]) - tmp.begin() + 1; if(a[i] < b[i]){ x[i] <<= 1; sh[t[i]].push_back({a[i], x[i]}); sh[t[i]].push_back({b[i], -x[i]}); } } for(int i = 1; i <= k; ++i) sort(sh[i].begin(), sh[i].end()); solve(); for(int i = 1; i <= q; ++i) l[i] = 200000002 - l[i]; for(int i = 1; i <= k; ++i) for(auto& x : sh[i]) if(x.ss > 0) x.ss = 200000002 - x.ss; else x.ss = -200000002 - x.ss; solve(); for(int i = 1; i <= q; ++i){ if(ans[i] > 400000002) cout<<"-1\n"; else cout<<ans[i] / 2<<'\n'; } }

컴파일 시 표준 에러 (stderr) 메시지

new_home.cpp: In function 'void solve()':
new_home.cpp:49:22: warning: variable 'it' set but not used [-Wunused-but-set-variable]
                 auto it = 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...