Submission #152021

#TimeUsernameProblemLanguageResultExecution timeMemory
152021junodeveloperRobots (IOI13_robots)C++14
0 / 100
61 ms63992 KiB
#include <bits/stdc++.h> #include "robots.h" #define sz(x) ((int)x.size()) #define all(x) (x).begin(), (x).end() #define fi first #define se second using namespace std; typedef long long ll; typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; const int offset=1<<20; int *val[2]; int tree[2][offset<<1]; vector<pii> st[2][1000010]; void Up(int t,int h) { while(h>0) { if(tree[t][h*2+1]==-1||(tree[t][h*2]!=-1&&val[t][tree[t][h*2]]>val[t][tree[t][h*2+1]])) tree[t][h]=tree[t][h*2]; else tree[t][h]=tree[t][h*2+1]; h/=2; } } void Add(int t,int p,int x,int i) { st[t][p].push_back({x,i}); } void Remove(int t,int p) { st[t][p].pop_back(); if(st[t][p].empty()) tree[t][p+offset]=-1; else tree[t][p+offset]=st[t][p].back().se; Up(t,(p+offset)/2); } int query(int t,int l,int r) { if(l>r) return -1; int ret=-1; l+=offset,r+=offset; while(1) { if(ret==-1||(tree[t][l]!=-1&&val[t][ret]<val[t][tree[t][l]])) ret=tree[t][l]; if(ret==-1||(tree[t][r]!=-1&&val[t][ret]<val[t][tree[t][r]])) ret=tree[t][r]; if(l==r) break; l=(l+1)>>1; r=(r-1)>>1; } return ret; } int putaway (int A, int B, int T, int X[], int Y[], int W[], int S[]) { int i,j; memset(tree,-1,sizeof(tree)); vector<int> v,w; sort(X,X+A); sort(Y,Y+B); val[0]=S,val[1]=W; for(i=0;i<T;i++) { v.push_back(W[i]); w.push_back(S[i]); } sort(all(v)); v.erase(unique(all(v)),v.end()); sort(all(w)); w.erase(unique(all(w)),w.end()); for(i=0;i<A;i++) { X[i]=lower_bound(all(v),X[i])-v.begin(); } for(i=0;i<B;i++) { Y[i]=lower_bound(all(w),Y[i])-w.begin(); } for(i=0;i<T;i++){ W[i]=lower_bound(all(v),W[i])-v.begin()+1; S[i]=lower_bound(all(w),S[i])-w.begin()+1; Add(0,W[i],S[i],i); Add(1,S[i],W[i],i); } for(i=1;i<=sz(v);i++) { sort(all(st[0][i])); tree[0][i+offset]=st[0][i].empty()?-1:st[0][i].back().se; } for(i=1;i<=sz(w);i++) { sort(all(st[1][i])); tree[1][i+offset]=st[1][i].empty()?-1:st[1][i].back().se; } int ans=0,q; bool flag; int cnt=0; while(1) { flag=false; for(i=0;T&&i<A;i++) { q=query(0,0,X[i]); if(q==-1) continue; Remove(0,W[q]); Remove(1,S[q]); T--; flag=true; } for(i=0;T&&i<B;i++) { q=query(1,0,Y[i]); if(q==-1) continue; Remove(0,W[q]); Remove(1,S[q]); T--; flag=true; } ans++; if(!T) break; if(!flag) { return -1; } } return ans; }

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:47:8: warning: unused variable 'j' [-Wunused-variable]
  int i,j;
        ^
robots.cpp:81:6: warning: unused variable 'cnt' [-Wunused-variable]
  int cnt=0;
      ^~~
#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...