Submission #255032

#TimeUsernameProblemLanguageResultExecution timeMemory
255032amoo_safarNew Home (APIO18_new_home)C++14
0 / 100
5104 ms165016 KiB
// Zende bad Shoma nasime faghat ! #include <bits/stdc++.h> #pragma GCC target ("avx2") #pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #pragma GCC optimize("unroll-loops") #define pb push_back #define F first #define S second #define all(x) x.begin(), x.end() #define debug(x) cerr << #x << " : " << x << '\n' using namespace std; typedef pair<int, int> pii; const int N = 3e5 + 10; const int Inf = 1e9; int n, q, k; int x[N], t[N], a[N], b[N]; int y[N], c[N], ans[N]; vector<int> V; map<int, int> mp[N]; set<int> rec[N]; int seg[N << 2]; /* void Ins(int id, int l, int r, int x, int L, int R){ if(r <= L || R <= l) return ; if(l <= L && R <= r){ seg[id].insert(x); return ; } int mid = (L + R) >> 1; Ins(id << 1, l, r, x, L, mid); Ins(id << 1 | 1, l, r, x, mid, R); } void Rem(int id, int l, int r, int x, int L, int R){ if(r <= L || R <= l) return ; if(l <= L && R <= r){ seg[id].erase(seg[id].find(x)); return ; } int mid = (L + R) >> 1; Rem(id << 1, l, r, x, L, mid); Rem(id << 1 | 1, l, r, x, mid, R); } */ void Set(int id, int idx, int v, int L, int R){ if(R - L == 1){ seg[id] = v; return ; } int mid = (L + R) >> 1; if(idx < mid) Set(id << 1, idx, v, L, mid); else Set(id << 1 | 1, idx, v, mid, R); seg[id] = min(seg[id << 1], seg[id << 1 | 1]); } int MN, MX, CNT; int Get(int id, int l, int r, int L, int R){ if(r <= L || R <= l) return Inf; if(l <= L && R <= r) return seg[id]; /*CNT += seg[id].size(); if(!seg[id].empty()){ MN = min(MN, *seg[id].begin()); MX = max(MX, *seg[id].rbegin()); }*/ int mid = (L + R) >> 1; return min(Get(id << 1, l, r, L, mid), Get(id << 1 | 1, l, r, mid, R)); //if(idx < mid) Get(id << 1, idx, L, mid); //else Get(id << 1 | 1, idx, mid, R); } template<typename T> T Prev(T A){return --A; }; template<typename T> T Next(T A){return ++A; }; pii GetRange(pii R){ return pii(R.F, upper_bound(all(V), R.S) - V.begin()); } pii GetRange(int tp, int pl){ set<int>::iterator it = rec[tp].find(pl); int resL = pl, resR; /* if(it == rec[tp].begin()) resL = 1; else resL = ( (*Prev(it)) + (*it)) / 2 + 1; */ if(Next(it) == rec[tp].end()) resR = 1e8; else resR = ( (*Next(it)) + (*it)) / 2; return pii(resL, resR); } void SegGet(int qn){ //cerr << "? " << pl << '\n'; int pl = y[qn]; MN = Get(1, (lower_bound(all(V), pl) - V.begin()), V.size(), 0, V.size()); //cerr << qn << ' ' << MN << '\n'; ans[qn] = max(ans[qn], pl - MN); //if(CNT != k) return -1; //return max(MX - pl, pl - MN); } multiset<int> ms[N]; void SegRem(int tp, int pl){ pii ran = GetRange(GetRange(tp, pl)); if(ran.S == 0) return ; ms[ran.S - 1].erase(ms[ran.S - 1].find(ran.F)); Set(1, ran.S - 1, (ms[ran.S - 1].empty() ? Inf : *ms[ran.S - 1].begin()), 0, V.size()); //Rem(1, ran.F, ran.S, pl, 0, V.size()); } void SegAdd(int tp, int pl){ pii ran = GetRange(GetRange(tp, pl)); if(ran.S == 0) return ; ms[ran.S - 1].insert(ran.F); //debug(ran.S - 1); Set(1, ran.S - 1, *ms[ran.S - 1].begin(), 0, V.size()); //Ins(1, ran.F, ran.S, pl, 0, V.size()); } void Add(int tp, int pl){ //cerr << "+ " << tp << ' ' << pl << '\n'; mp[tp][pl] ++; if(mp[tp][pl] > 1) return ; auto it = rec[tp].lower_bound(pl); int la = -1; //if(it != rec[tp].end()) nx = *it; if(it != rec[tp].begin()) la = *Prev(it); //if(nx != -1) SegRem(tp, nx); if(la != -1) SegRem(tp, la); rec[tp].insert(pl); //if(nx != -1) SegAdd(tp, nx); if(la != -1) SegAdd(tp, la); SegAdd(tp, pl); } void Erase(int tp, int pl){ //cerr << "- " << tp << ' ' << pl << '\n'; mp[tp][pl] --; if(mp[tp][pl] > 0) return ; auto it = rec[tp].find(pl); int la = -1; //if(Next(it) != rec[tp].end()) nx = *Next(it); if(it != rec[tp].begin()) la = *Prev(it); //if(nx != -1) SegRem(tp, nx); if(la != -1) SegRem(tp, la); SegRem(tp, pl); rec[tp].erase(pl); //if(nx != -1) SegAdd(tp, nx); if(la != -1) SegAdd(tp, la); } vector<int> Ea[N], Er[N], Eq[N]; int flg[N], open[N], cntn; int main(){ ios::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]; b[i] ++; V.pb(a[i]); V.pb(b[i]); } for(int i = 1; i <= q; i++){ cin >> y[i] >> c[i]; } sort(all(V)); V.resize(unique(all(V)) - V.begin()); int AllT = V.size(); for(int i = 1; i <= n; i++){ a[i] = lower_bound(all(V), a[i]) - V.begin(); b[i] = lower_bound(all(V), b[i]) - V.begin(); Ea[a[i]].pb(i); Er[b[i]].pb(i); //cerr << "!!! " << a[i] << ' ' << b[i] << '\n'; } for(int i = 1; i <= q; i++){ if(c[i] < V[0]){ ans[i] = -1; continue; } c[i] = (upper_bound(all(V), c[i]) - V.begin() ) - 1; Eq[c[i]].pb(i); //cerr << "? " << c[i] << '\n'; } V.clear(); //for(int i = 1; i <= n; i++) V.pb(x[i]); for(int i = 1; i <= q; i++) V.pb(y[i]); sort(all(V)); V.resize(unique(all(V)) - V.begin()); memset(seg, 31, sizeof seg); for(int tm = 0; tm < AllT; tm++){ for(auto i : Ea[tm]){ Add(t[i], x[i]); open[t[i]] ++; if(open[t[i]] == 1) cntn ++; } for(auto i : Er[tm]){ Erase(t[i], x[i]); open[t[i]] --; if(open[t[i]] == 0) cntn --; } for(auto i : Eq[tm]){ SegGet(i); //cerr << i << ' ' << c if(cntn < k) flg[i] = true; } //cerr << '\n'; } int SM = 100000001; for(int i = 1; i <= n; i ++) x[i] = SM - x[i]; for(int i = 1; i <= n; i ++) y[i] = SM - y[i]; for(auto &x : V) if(x < SM) x = SM - x; sort(all(V)); V.resize(unique(all(V)) - V.begin()); memset(seg, 31, sizeof seg); for(int tm = 0; tm < AllT; tm++){ for(auto i : Ea[tm]) Add(t[i], x[i]); for(auto i : Er[tm]) Erase(t[i], x[i]); for(auto i : Eq[tm]) SegGet(i); //cerr << '\n'; } for(int i = 1; i <= q; i++) cout << (flg[i] ? -1 : ans[i]) << '\n'; return 0; } /* 4 2 4 3 1 1 10 9 2 2 4 7 2 5 7 4 1 8 10 5 3 5 6 5 9 1 10 2 1 3 1 1 1 4 1 1 2 6 1 3 1 5 1 7 1 1 1 100000000 1 1 1 1 1 */
#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...