Submission #60832

#TimeUsernameProblemLanguageResultExecution timeMemory
60832dualityNew Home (APIO18_new_home)C++11
5 / 100
5106 ms143864 KiB
#define DEBUG 0 #include <bits/stdc++.h> using namespace std; #if DEBUG // basic debugging macros int __i__,__j__; #define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl #define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl #define printVar(n) cout<<#n<<": "<<n<<endl #define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl #define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;} #define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;} // advanced debugging class // debug 1,2,'A',"test"; class _Debug { public: template<typename T> _Debug& operator,(T val) { cout << val << endl; return *this; } }; #define debug _Debug(), #else #define printLine(l) #define printLine2(l,c) #define printVar(n) #define printArr(a,l) #define print2dArr(a,r,c) #define print2dArr2(a,r,c,l) #define debug #endif // define #define MAX_VAL 999999999 #define MAX_VAL_2 999999999999999999LL #define EPS 1e-6 #define mp make_pair #define pb push_back // typedef typedef unsigned int UI; typedef long long int LLI; typedef unsigned long long int ULLI; typedef unsigned short int US; typedef pair<int,int> pii; typedef pair<LLI,LLI> plli; typedef vector<int> vi; typedef vector<LLI> vlli; typedef vector<pii> vpii; typedef vector<plli> vplli; // ---------- END OF TEMPLATE ---------- struct op { int time,t,x; }; bool comp(op a,op b) { if (a.time == b.time) return a.t < b.t; else return a.time < b.time; } vi sorted; vector<op> oper; multiset<int> stores[300000]; multimap<pii,int> M; vpii tree[1 << 19]; int ans[300000]; int update(int s,int e,int as,int ae,int i,pii p) { if (as > ae) return 0; else if ((s > ae) || (e < as)) return 0; else if ((s >= as) && (e <= ae)) { tree[i].pb(p); return 0; } int mid = (s+e) / 2; update(s,mid,as,ae,2*i+1,p); update(mid+1,e,as,ae,2*i+2,p); return 0; } int query(int s,int e,int q,int i,pii p) { if ((s > q) || (e < q)) return 0; else if (s == e) { tree[i].pb(p); return 0; } int mid = (s+e) / 2; query(s,mid,q,2*i+1,p); query(mid+1,e,q,2*i+2,p); tree[i].pb(p); return 0; } int solve(int s,int e,int i) { int j,k; for (j = 0; j < tree[i].size(); j++) { if (tree[i][j].second < 0) { int p = -tree[i][j].second-1; for (k = 0; k < tree[i].size(); k++) { if (tree[i][k].second >= 0) ans[p] = max(ans[p],tree[i][k].second-abs(tree[i][j].first-tree[i][k].first)); } } } if (s != e) { int mid = (s+e) / 2; solve(s,mid,2*i+1),solve(mid+1,e,2*i+2); } return 0; } /*map<int,int> M; int query(int x) { auto it = M.lower_bound(x); int m = 0; if (it != M.end()) m = max(m,it->second-(it->first-x)); if (it != M.begin()) it--,m = max(m,it->second-(x-it->first)); return m; } int update(int x,int h) { //cout<<"UPDATE "<<x<<","<<h<<endl; if (query(x) >= h) return 0; //cout<<"XXX"<<endl; auto it = M.lower_bound(x); while (it != M.end()) { if (it->second > h-(it->first-x)) break; else it = M.erase(it); } M[x] = h; it = M.find(x); while (1) { if (it == M.begin()) break; it--; if (it->second > h-(x-it->first)) break; else it = M.erase(it); } return 0; } multiset<pii> M2;*/ int main() { int i; int n,k,q; int x,t,a,b,l,y; scanf("%d %d %d",&n,&k,&q); sorted.pb(0),sorted.pb(3e8); for (i = 0; i < n; i++) { scanf("%d %d %d %d",&x,&t,&a,&b); oper.pb((op){a,t,x}); oper.pb((op){b+1,-t,x}); sorted.pb(a),sorted.pb(b+1); } sort(oper.begin(),oper.end(),comp); sort(sorted.begin(),sorted.end()); sorted.resize(unique(sorted.begin(),sorted.end())-sorted.begin()); for (i = 0; i < k; i++) { stores[i].insert(-3e8),stores[i].insert(3e8); M.insert(mp(mp(0,6e8),0)); } for (i = 0; i < oper.size(); i++) { oper[i].time = lower_bound(sorted.begin(),sorted.end(),oper[i].time)-sorted.begin(); if (oper[i].t > 0) { auto it = stores[oper[i].t-1].lower_bound(oper[i].x); auto it2 = it; it2--; auto it3 = M.find(mp(*it+*it2,*it-*it2)); update(0,sorted.size()-2,it3->second,oper[i].time-1,0,mp(*it+*it2,*it-*it2)); M.erase(it3); M.insert(mp(mp(*it+oper[i].x,*it-oper[i].x),oper[i].time)); M.insert(mp(mp(oper[i].x+*it2,oper[i].x-*it2),oper[i].time)); stores[oper[i].t-1].insert(oper[i].x); } else { auto it = stores[-oper[i].t-1].lower_bound(oper[i].x); auto it2 = it; it2--; auto it3 = M.find(mp(*it+*it2,*it-*it2)); update(0,sorted.size()-2,it3->second,oper[i].time-1,0,mp(*it+*it2,*it-*it2)); M.erase(it3); it++,it2++; it3 = M.find(mp(*it+*it2,*it-*it2)); update(0,sorted.size()-2,it3->second,oper[i].time-1,0,mp(*it+*it2,*it-*it2)); M.erase(it3); it2--; M.insert(mp(mp(*it+*it2,*it-*it2),oper[i].time)); stores[-oper[i].t-1].erase(--it); } } while (!M.empty()) { update(0,sorted.size()-2,M.begin()->second,sorted.size()-2,0,M.begin()->first); M.erase(M.begin()); } for (i = 0; i < q; i++) { scanf("%d %d",&l,&y); int p = upper_bound(sorted.begin(),sorted.end(),y)-sorted.begin()-1; query(0,sorted.size()-2,p,0,mp(2*l,-(i+1))); } solve(0,sorted.size()-2,0); for (i = 0; i < q; i++) printf("%d\n",(ans[i] > 3e8) ? -1:ans[i]/2); return 0; }

Compilation message (stderr)

new_home.cpp: In function 'int solve(int, int, int)':
new_home.cpp:97:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (j = 0; j < tree[i].size(); j++) {
                 ~~^~~~~~~~~~~~~~~~
new_home.cpp:100:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (k = 0; k < tree[i].size(); k++) {
                         ~~^~~~~~~~~~~~~~~~
new_home.cpp: In function 'int main()':
new_home.cpp:158:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < oper.size(); i++) {
                 ~~^~~~~~~~~~~~~
new_home.cpp:143: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:146: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:192: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...