Submission #1036947

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036947		aaaaaarroz	Robots (IOI13_robots)	C++17	14 / 100	206 ms	17040 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
template<class T, T m_(T, T)> struct IterativeSegmentTree{
  int n; vector<T> ST;
  IterativeSegmentTree(){}
  IterativeSegmentTree(vector<T> &a){
    n = a.size(); ST.resize(n << 1);
    for (int i=n;i<(n<<1);i++)ST[i]=a[i-n];
    for (int i=n-1;i>0;i--)ST[i]=m_(ST[i<<1],ST[i<<1|1]);
  }
  void update(int pos, T val){ // replace with val
    ST[pos += n] = val;
    for (pos >>= 1; pos > 0; pos >>= 1)
      ST[pos] = m_(ST[pos<<1], ST[pos<<1|1]);
  }
  T query(int l, int r){ // [l, r]
    T ansL, ansR; bool hasL = 0, hasR = 0;
    for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
      if (l & 1) 
        ansL=(hasL?m_(ansL,ST[l++]):ST[l++]),hasL=1;
      if (r & 1) 
        ansR=(hasR?m_(ST[--r],ansR):ST[--r]),hasR=1;
    }
    if (!hasL) return ansR; if (!hasR) return ansL;
    return m_(ansL, ansR);
  }
};
pair<int,int> merge(pair<int,int> a, pair<int,int> b){
    if(a.first<b.first){
		return a;
	}
	else{
		return b;
	}
}
int merge2(int a, int b){
    return max(a,b);
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]){
	sort(X,X+A);
	sort(Y,Y+B);
	sort(W,W+T);
	reverse(W,W+T);
	sort(S,S+T);
	reverse(S,S+T);
	vector<pair<int,int>>x(A);
	for(int i=0;i<A;i++){
		x[i].first=0;
		x[i].second=i;
	}
	vector<pair<int,int>>y(B);
	for(int i=0;i<B;i++){
		y[i].first=0;
		y[i].second=i;
	}
	vector<int>xl(A,0);
	vector<int>yl(B,0);
	IterativeSegmentTree<pair<int,int>,merge>XX(x);
	IterativeSegmentTree<pair<int,int>,merge>YY(y);
	IterativeSegmentTree<int,merge2>max_x(xl);
	IterativeSegmentTree<int,merge2>max_y(yl);
	for(int i=0;i<T;i++){
		int weight=W[i];
		int size=S[i];
		auto itr1=upper_bound(X,X+A,weight);
		auto itr2=upper_bound(Y,Y+B,size);
		if(itr1==X+A&&itr2==Y+B){
			return -1;
		}
		else if(itr2==Y+B){
			int pos_w=itr1-X;
			pair<int,int>mejor_w=XX.query(pos_w,A-1);
			XX.update(mejor_w.second,{mejor_w.first+1,mejor_w.second});
			max_x.update(mejor_w.second,(mejor_w.first+1));
		}
		else if(itr1==X+A){
			int pos_s=itr2-Y;
			pair<int,int>mejor_s=YY.query(pos_s,B-1);
			YY.update(mejor_s.second,{mejor_s.first+1,mejor_s.second});
			max_x.update(mejor_s.second,(mejor_s.first+1));
		}
		else{ 
			int pos_w=itr1-X;
			int pos_s=itr2-Y;
			pair<int,int>mejor_w=XX.query(pos_w,A-1);
			pair<int,int>mejor_s=YY.query(pos_s,B-1);
			if(mejor_w.first<=mejor_s.second){
				XX.update(mejor_w.second,{mejor_w.first+1,mejor_w.second});
				max_x.update(mejor_w.second,(mejor_w.first+1));
			}
			else{
				YY.update(mejor_s.second,{mejor_s.first+1,mejor_s.second});
				max_x.update(mejor_s.second,(mejor_s.first+1));
			}
		}
	}
	return max(max_x.query(0,A-1),max_y.query(0,B-1));
}

Compilation message (stderr)

robots.cpp: In member function 'T IterativeSegmentTree<T, m_>::query(int, int)':
robots.cpp:25:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   25 |     if (!hasL) return ansR; if (!hasR) return ansL;
      |     ^~
robots.cpp:25:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   25 |     if (!hasL) return ansR; if (!hasR) return ansL;
      |                             ^~
robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:18:13: warning: 'ansR' may be used uninitialized in this function [-Wmaybe-uninitialized]
   18 |     T ansL, ansR; bool hasL = 0, hasR = 0;
      |             ^~~~
robots.cpp:18:13: warning: 'ansR' may be used uninitialized in this function [-Wmaybe-uninitialized]

• Subtask 1: 0 / 14
• Subtask 2: 14 / 14
• Subtask 3: 0 / 25
• Subtask 4: 0 / 37
• Subtask 5: 0 / 10