제출 #257894

#제출 시각아이디문제언어결과실행 시간메모리
257894ChrisT로봇 (IOI13_robots)C++17
76 / 100
1773 ms65536 KiB
#include <algorithm> #include <vector> #include <map> #include "robots.h" using namespace std; using ll = long long; using pii = pair<int,int>; #define lc ind<<1 #define rc ind<<1|1 const int MN = 1e6 + 5, LOG = 18, MOD = 1e9 + 7; struct Point { int x,y; bool operator< (const Point &o) const { return make_pair(x,y) < make_pair(o.x,o.y); } }; bool cmp (const Point &a, const Point &b) {return make_pair(a.y,a.x) < make_pair(b.y,b.x);} struct Segtree { pii tree[2097155]; void build (int ind, int l, int r, vector<int> &v) { if (l == r) return (void) (tree[ind] = {v[l-1],l-1}); int mid = (l + r) / 2; build(lc,l,mid,v); build(rc,mid+1,r,v); tree[ind] = max(tree[lc],tree[rc]); } int findfirst (int ind, int l, int r) { if (l == r) return tree[ind].first > 0 ? l-1 : -1; int mid = (l + r) / 2; if (tree[lc].first > 0) return findfirst(lc,l,mid); return findfirst(rc,mid+1,r); } void update (int ind, int l, int r, int i, int v) { if (l == r) return (void) (tree[ind] = {v,l-1}); int mid = (l + r) / 2; if (i <= mid) update(lc,l,mid,i,v); else update(rc,mid+1,r,i,v); tree[ind] = max(tree[lc],tree[rc]); } pii query (int ind, int tl, int tr, int l, int r) { if (tl > r || tr < l) return {-1,-1}; if (l <= tl && tr <= r) return tree[ind]; int mid = (tl + tr) / 2; return max(query(lc,tl,mid,l,r),query(rc,mid+1,tr,l,r)); } } xSeg, ySeg; int putaway (int a, int b, int t, int *x, int *y, int *w, int *s) { //2 segtree + bsearch sort(x,x+a); sort(y,y+b); vector<Point> xSrt(t), ySrt(t); for (int i = 0; i < t; i++) xSrt[i] = ySrt[i] = {w[i],s[i]}; sort(xSrt.begin(),xSrt.end()); sort(ySrt.begin(),ySrt.end(),cmp); vector<int> temp(t); for (int i = 0; i < t; i++) temp[i] = xSrt[i].y; xSeg.build(1,1,t,temp); for (int i = 0; i < t; i++) temp[i] = ySrt[i].x; ySeg.build(1,1,t,temp); map<Point,int> taken; auto del = [&] (Point &p) { //printf ("p {%d,%d}\n",p.x,p.y); int posX = lower_bound(xSrt.begin(),xSrt.end(),p) - xSrt.begin() + taken[p]; int posY = lower_bound(ySrt.begin(),ySrt.end(),p,cmp) - ySrt.begin() + taken[p]; taken[p]++; //printf ("posX %d posY %d\n",posX,posY); xSeg.update(1,1,t,posX+1,-1e9); ySeg.update(1,1,t,posY+1,-1e9); }; int ret = 0, done = 0; while (done < t) { ++ret; bool add = 0; int lstLine = -1; while (1) { int go = xSeg.findfirst(1,1,t); //printf ("go %d\n",go); if (go == -1) break; int nxtLine = max(lstLine + 1,(int)(upper_bound(x,x+a,xSrt[go].x)-x)); //printf ("nxtLine %d\n",nxtLine); if (nxtLine >= a) break; int ed = lower_bound(xSrt.begin(),xSrt.end(),Point{x[nxtLine],0})-xSrt.begin(); //printf ("ed %d\n",ed); int take = xSeg.query(1,1,t,1,ed).second; //printf ("take %d\n",take); del(xSrt[take]); add = 1; ++done; lstLine = nxtLine; } lstLine = -1; while (1) { int go = ySeg.findfirst(1,1,t); //printf ("y go %d\n",go); if (go == -1) break; int nxtLine = max(lstLine + 1,(int)(upper_bound(y,y+b,ySrt[go].y)-y)); //printf ("y nxtLine %d\n",nxtLine); if (nxtLine >= b) break; int ed = lower_bound(ySrt.begin(),ySrt.end(),Point{0,y[nxtLine]},cmp)-ySrt.begin(); //printf ("y ed %d\n",ed); int take = ySeg.query(1,1,t,1,ed).second; //printf ("y take %d\n",take); del(ySrt[take]); add = 1; ++done; lstLine = nxtLine; } if (!add) return -1; } return ret; }
#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...