Submission #1031042

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031042		vjudge1	Robots (IOI13_robots)	C++17	76 / 100	865 ms	23928 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;

struct{
    int*tree,*inds;
    int*p,n;
    void init(int*P,int*PP,int N){
        p=P,n=N;
        tree=new int[4*N];
        inds=PP;
        build(0,n-1,1);
    }
    int build(int l,int r,int node){
        if(l==r){
            return tree[node]=p[inds[l]];
        }
        int mid=(l+r)>>1,child=node<<1;
        return tree[node]=max(build(l,mid,child),build(mid+1,r,child|1));
    }
    int L,R;
    int query(int l,int r,int node){
        if(r<L||R<l){
            return INT_MIN;
        }
        if(L<=l&&r<=R){
            return tree[node];
        }
        int mid=(l+r)>>1,child=node<<1;
        return max(query(l,mid,child),query(mid+1,r,child|1));
    }
    int query(int l,int r){
        L=l,R=r;
        return query(0,n-1,1);
    }
    int P;
    int walk(int l,int r,int node){
        if(l==r){
            return inds[l];
        }
        int mid=(l+r)>>1,child=node<<1;
        if(P<=mid)return walk(l,mid,child);
        int val1=tree[child];
        int val2=query(mid+1,min(r,P));
        if(val2<val1)return walk(l,mid,child);
        return walk(mid+1,r,child|1);
    }
    int walk(int p){
        P=p;
        return walk(0,n-1,1);
    }
    void update(int l,int r,int node){
        if(l==r){
            tree[node]=INT_MIN;
            return;
        }
        int mid=(l+r)>>1,child=node<<1;
        if(P<=mid)update(l,mid,child);
        else update(mid+1,r,child|1);
        tree[node]=max(tree[child],tree[child|1]);
    }
    void update(int p){
        P=p;
        update(0,n-1,1);
    }
}st1,st2;

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    sort(X,X+A);
    sort(Y,Y+B);
    for(int i=0;i<T;i++){
        if((!A||X[A-1]<=W[i])&&(!B||Y[B-1]<=S[i])){
            return -1;
        }
    }
    int P1[T];
    for(int i=0;i<T;i++)P1[i]=i;
    sort(P1,P1+T,[&](int i,int j)->bool {
        return W[i]<W[j];
    });
    int T1[T];
    for(int i=0;i<T;i++)T1[P1[i]]=i;
    st1.init(S,P1,T);
    int can=-1;
    multiset<int>ms1;
    for(int i=0;i<A;i++){
        while(can+1<T&&W[P1[can+1]]<X[i]){
            can++;
        }
        if(can!=-1){
            ms1.insert(can);
        }
    }
    int P2[T];
    for(int i=0;i<T;i++)P2[i]=i;
    sort(P2,P2+T,[&](int i,int j)->bool {
        return S[i]<S[j];
    });
    int T2[T];
    for(int i=0;i<T;i++)T2[P2[i]]=i;
    st2.init(W,P2,T);
    can=-1;
    multiset<int>ms2;
    for(int i=0;i<B;i++){
        while(can+1<T&&S[P2[can+1]]<Y[i]){
            can++;
        }
        if(can!=-1){
            ms2.insert(can);
        }
    }
    bool died[T];
    memset(died,0,T);
    int left=T,turn=0;
    while(left){
        turn++;
        vector<int>torem;
        for(int i:ms1){
            //cerr<<i<<" :: ";
            int val=st1.walk(i);
            if(died[val]){
                //cerr<<"failed\n";
                torem.push_back(i);
            }else{
                //cerr<<"killed "<<val<<" { "<<T1[val]<<" "<<T2[val]<<" }\n";
                died[val]=1;
                st1.update(T1[val]);
                st2.update(T2[val]);
                left--;
            }
        }
        for(int i:torem){
            ms1.erase(i);
        }
        //cerr<<"\n";
        torem.clear();
        for(int i:ms2){
            //cerr<<i<<" :: ";
            int val=st2.walk(i);
            if(died[val]){
                //cerr<<"failed\n";
                torem.push_back(i);
            }else{
                //cerr<<"killed "<<val<<" { "<<T1[val]<<" "<<T2[val]<<" }\n";
                died[val]=1;
                st1.update(T1[val]);
                st2.update(T2[val]);
                left--;
            }
        }
        for(int i:torem){
            ms2.erase(i);
        }
        //cerr<<"\n-----------------\n";
    }
    return turn;
}

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