제출 #60899

#제출 시각아이디문제언어결과실행 시간메모리
60899duality새 집 (APIO18_new_home)C++11
57 / 100
5107 ms293640 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 ---------- int readInt() { char c; while ((c=getchar()) < '0'); int n = c-'0'; while ((c=getchar()) >= '0') n *= 10,n += c-'0'; return n; } struct event { int time,x,t; }; bool comp(event a,event b) { if (a.time == b.time) return a.t < b.t; else return a.time < b.time; } vi sorted; vector<event> events[300000]; map<int,int> S; map<pii,int> M; vector<pair<pii,pii> > oper; vpii tree[600000]; int ans[300000]; int update(int as,int ae,pii p) { as += sorted.size(),ae += sorted.size()+1; while (as < ae) { if (as & 1) tree[as++].pb(p); if (ae & 1) tree[--ae].pb(p); as >>= 1,ae >>= 1; } return 0; } int query(int q,pii p) { q += sorted.size(); while (q > 0) tree[q].pb(p),q >>= 1; return 0; } int main() { int i,j; int n,k,q; int x,t,a,b,l,y; n = readInt(),k = readInt(),q = readInt(); for (i = 0; i < n; i++) { x = readInt(),t = readInt()-1,a = readInt(),b = readInt(); events[t].pb((event){a,x,1}); events[t].pb((event){b+1,x,-1}); } for (i = 0; i < k; i++) { sort(events[i].begin(),events[i].end(),comp); S[-3e8] = S[3e8] = 1,M[mp(0,6e8)] = 0; for (j = 0; j < events[i].size(); j++) { if (events[i][j].t == 1) { auto it = S.lower_bound(events[i][j].x); if (it->first == events[i][j].x) { it->second++; continue; } auto it2 = it; it2--; pii p = mp(it->first+it2->first,it->first-it2->first); auto it3 = M.find(p); oper.pb(mp(p,mp(it3->second,events[i][j].time))); it3 = M.erase(it3); it3 = M.insert(it3,mp(mp(it->first+events[i][j].x,it->first-events[i][j].x),events[i][j].time)); M.insert(it3,mp(mp(events[i][j].x+it2->first,events[i][j].x-it2->first),events[i][j].time)); S.insert(it,mp(events[i][j].x,1)); } else { auto it = S.find(events[i][j].x); if (it->second > 1) { it->second--; continue; } auto it2 = it; it2--; pii p = mp(it->first+it2->first,it->first-it2->first); auto it3 = M.find(p); oper.pb(mp(p,mp(it3->second,events[i][j].time))); it3 = M.erase(it3); it++,it2++,p = mp(it->first+it2->first,it->first-it2->first); oper.pb(mp(p,mp(it3->second,events[i][j].time))); it3 = M.erase(it3); it2--,p = mp(it->first+it2->first,it->first-it2->first); M.insert(it3,mp(p,events[i][j].time)); S.erase(--it); } } for (auto it = M.begin(); it != M.end(); it++) oper.pb(mp(it->first,mp(it->second,3e8))); S.clear(),M.clear(); } for (i = 0; i < q; i++) { l = readInt(),y = readInt(); sorted.pb(y); oper.pb(mp(mp(2*l,-(i+1)),mp(y,-1))); } sort(oper.begin(),oper.end()); sort(sorted.begin(),sorted.end()); sorted.resize(unique(sorted.begin(),sorted.end())-sorted.begin()); for (i = 0; i < oper.size(); i++) { if (oper[i].second.second == -1) { oper[i].second.first = lower_bound(sorted.begin(),sorted.end(),oper[i].second.first)-sorted.begin(); query(oper[i].second.first,oper[i].first); } else { oper[i].second.first = lower_bound(sorted.begin(),sorted.end(),oper[i].second.first)-sorted.begin(); oper[i].second.second = lower_bound(sorted.begin(),sorted.end(),oper[i].second.second)-sorted.begin()-1; if (oper[i].second.first <= oper[i].second.second) update(oper[i].second.first,oper[i].second.second,oper[i].first); } } for (i = 1; i < 2*sorted.size(); i++) { pii m = mp(-3e8,0); for (j = 0; j < tree[i].size(); j++) { if (tree[i][j].second >= 0) { if (tree[i][j].second > m.second-(tree[i][j].first-m.first)) m = tree[i][j]; } else ans[-tree[i][j].second-1] = max(ans[-tree[i][j].second-1],m.second-(tree[i][j].first-m.first)); } m = mp(3e8,0); for (j = tree[i].size()-1; j >= 0; j--) { if (tree[i][j].second >= 0) { if (tree[i][j].second > m.second-(m.first-tree[i][j].first)) m = tree[i][j]; } else ans[-tree[i][j].second-1] = max(ans[-tree[i][j].second-1],m.second-(m.first-tree[i][j].first)); } } for (i = 0; i < q; i++) printf("%d\n",(ans[i] > 3e8) ? -1:ans[i]/2); return 0; }

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

new_home.cpp: In function 'int main()':
new_home.cpp:104:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < events[i].size(); j++) {
                     ~~^~~~~~~~~~~~~~~~~~
new_home.cpp:152:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < oper.size(); i++) {
                 ~~^~~~~~~~~~~~~
new_home.cpp:163:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 1; i < 2*sorted.size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~
new_home.cpp:165:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < tree[i].size(); j++) {
                     ~~^~~~~~~~~~~~~~~~
#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...