| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 28000 | repeating | Robots (IOI13_robots) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
//#include "robots.h"
#define F first
#define S second
#define P push
#define pb push_back
#define MEM(dp,i) memset(dp,i,sizeof(dp))
#define W while
#define R return
#define C continue
#define SI size()
#define ll long long
#define ld long double
#define pll pair<ll,ll>
#define pii pair<int,int>
#define SF(x) scanf("%I64d",&x)
#define SF2(x,y) scanf("%I64d%I64d",&x,&y)
#define SF3(x,y,z) scanf("%I64d%I64d%I64d",&x,&y,&z)
#define SF4(x,y,z,o) scanf("%I64d%I64d%I64d%I64d",&x,&y,&z,&o)
#define all(v) v.begin(),v.end()
using namespace std;
const long long INF = 1e9;
const int MX=1000005;
vector<int> v1,v2;
int n,A,B,X[50005],Y[50005],w[MX],s[MX];
bool cmp1(int a,int b){
if(w[a]==w[b])R s[a]>s[b];
R w[a]<w[b];
}
bool cmp2(int a,int b){
if(s[a]==s[b])R w[a]>w[b];
R s[a]<s[b];
}
int seg1[MX*4],seg2[MX*4];
int ind1[MX],ind2[MX];
int sum=0;
void u1(int node,int l,int r,int ind,int val){
if(ind<l||r<ind)R;
if(l==r){
seg1[node]=val;
R;
}
u1(node*2,l,(l+r)/2,ind,val);
u1(node*2+1,(l+r)/2+1,r,ind,val);
if(seg1[node*2]==n&&seg1[node*2+1]==n){
seg1[node]=n;
R;
}
if(s[seg1[node*2]]>s[seg1[node*2+1]])
seg1[node]=seg1[node*2];
else
seg1[node]=seg1[node*2+1];
// cout<<l<<" "<<r<<" "<<ind<<" "<<val<<" "<<sum<<" "<<seg1[node]<<endl;
}
void u2(int node,int l,int r,int ind,int val){
if(ind<l||r<ind)R;
if(l==r){
seg2[node]=val;
R;
}
u2(node*2,l,(l+r)/2,ind,val);
u2(node*2+1,(l+r)/2+1,r,ind,val);
if(seg2[node*2]==n&&seg2[node*2+1]==n){
seg2[node]=n;
R;
}
if(w[seg2[node*2]]>w[seg2[node*2+1]])
seg2[node]=seg2[node*2];
else
seg2[node]=seg2[node*2+1];
}
int q1(int node,int l,int r,int st,int e){
if(e<l||r<st)R n;
if(st<=l&&r<=e){
if(l==r)R seg1[node];
// if(sum==7)
// cout<<l<<" "<<r<<" "<<seg1[node]<<" "<<seg1[node*2]<<endl;
if(seg1[node]==seg1[node*2])R q1(node*2,l,(l+r)/2,st,e);
else R q1(node*2+1,(l+r)/2+1,r,st,e);
}
else{
int i1=q1(node*2,l,(l+r)/2,st,e),i2=q1(node*2+1,(l+r)/2+1,r,st,e);
// if(sum==7)
// cout<<l<<" "<<r<<" "<<i1<<" "<<i2<<" "<<s[i1]<<" "<<s[i2]<<endl;
if(s[i1]>s[i2])R i1;
else R i2;
}
}
int q2(int node,int l,int r,int st,int e){
if(e<l||r<st)R n;
if(st<=l&&r<=e){
if(l==r){R seg2[node];}
// cout<<l<<" "<<r<<"s"<<seg2[node]<<" "<<seg2[node*2]<<endl;
if(seg2[node]==seg2[node*2])R q2(node*2,l,(l+r)/2,st,e);
else R q2(node*2+1,(l+r)/2+1,r,st,e);
}
else{
int i1=q2(node*2,l,(l+r)/2,st,e),i2=q2(node*2+1,(l+r)/2+1,r,st,e);
// cout<<l<<" "<<r<<" "<<i1<<" "<<i2<<" "<<s[i1]<<" "<<s[i2]<<endl;
if(w[i1]>w[i2])R i1;
else R i2;
}
}
multiset<int> m1,m2;
vector<int> vec1,vec2;
int bs1(int x){
int ret=-1;
int l=0,r=n;
W(l<r){
int mid=(l+r)/2;
if(vec1[mid]<x){
l=mid+1;
ret=mid;
}
else r=mid;
}
R ret;
}
int bs2(int x){
int ret=-1;
int l=0,r=n;
W(l<r){
int mid=(l+r)/2;
if(vec2[mid]<x){
l=mid+1;
ret=mid;
}
else r=mid;
}
R ret;
}
int putaway(int A_, int B_, int N, int X_[], int Y_[], int w_[], int s_[]) {
A=A_,B=B_,n=N;
for(int i=0;i<A;i++)
X[i]=X_[i];
for(int i=0;i<B;i++)
Y[i]=Y_[i];
for(int i=0;i<n;i++)
w[i]=w_[i],s[i]=s_[i];
for(int i=0;i<n;i++){
v1.pb(i);
v2.pb(i);
}
sort(all(v1),cmp1);
sort(all(v2),cmp2);
sort(X,X+A);
sort(Y,Y+B);
for(int i=0;i<n;i++){
ind1[v1[i]]=i;
ind2[v2[i]]=i;
vec1.pb(w[i]);
vec2.pb(s[i]);
}
sort(all(vec1));
sort(all(vec2));
for(int i=0;i<n;i++){
u1(1,0,n-1,i,v1[i]);
u2(1,0,n-1,i,v2[i]);
}
for(int i=0;i<A;i++)
m1.insert(X[i]);
for(int i=0;i<B;i++)
m2.insert(Y[i]);
int res=0;
W(sum<n){
vector<int> vec;
if(m1.empty()&&m2.empty())R -1;
if(!m1.empty()){
int x;
for(auto i : m1){
x=bs1(i);
// cout<<x<<endl;
if(x==-1){
// cout<<'z';
vec.pb(i);
C;
}
x=q1(1,0,n-1,0,x);
// cout<<x<<" ";
if(x==n){
vec.pb(i);
// cout<<'z';
}
else{
u1(1,0,n-1,ind1[x],n);
u2(1,0,n-1,ind2[x],n);
sum++;
}
}
for(auto i : vec){
m1.erase(i);
}
}
// cout<<'s';
vec.clear();
if(!m2.empty()){
int x;
for(auto i : m2){
x=bs2(i);
if(x==-1){
// cout<<'r';
vec.pb(i);
C;
}
x=q2(1,0,n-1,0,x);
// cout<<x<<" ";
if(x==n){
vec.pb(i);
// cout<<'z';
}
else{
u1(1,0,n-1,ind1[x],n);
u2(1,0,n-1,ind2[x],n);
sum++;
}
}
for(auto i : vec){
m1.erase(i);
}
}
for(auto i : vec)
m2.erase(i);
vec.clear();
res++;
}
return res;
}
#include <stdio.h>
#include <stdlib.h>
//#include "robots.h"
#define fail(s, x...) do { \
fprintf(stderr, s "\n", ## x); \
exit(1); \
} while(0)
#define MAX_A 50000
#define MAX_B 50000
#define MAX_T 500000
static int X_[MAX_A];
static int Y_[MAX_B];
static int W_[MAX_T];
static int S_[MAX_T];
int main() {
int A, B, T, i;
int res;
res = scanf( "%d", &A);
res = scanf( "%d", &B);
res = scanf( "%d", &T);
for (i = 0; i < A; i++) {
res = scanf( "%d", &X_[i]);
}
for (i = 0; i < B; i++) {
res = scanf( "%d", &Y_[i]);
}
for (i = 0; i < T; i++) {
res = scanf( "%d%d", &W_[i], &S_[i]);
}
int answer = putaway(A, B, T, X_, Y_, W_, S_);
printf("%d\n", answer);
return 0;
}