Submission #1131842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131842		t9unkubj	Robots (IOI13_robots)	C++20	100 / 100	2294 ms	60632 KiB

robots

#include "robots.h"
#ifdef t9unkubj
#include"debug.cpp"
//#include"template_no_debug.h"
#else 
#define dbg(...) 199958
#endif

#undef _GLIBCXX_DEBUG
#pragma GCC optimize("O3")
using namespace std;
#include<bits/stdc++.h>
using ll=long long;
using ull=unsigned long long;
template<class T>using vc=vector<T>;
template<class T>using vvc=vc<vc<T>>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++)
#define DREP(i,n,m) for(ll i=(n);i>=(m);i--)
#define drep(i,n) for(ll i=((n)-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
template<class T,class F>
bool chmin(T &x, F y){
    if(x>y){
        x=y;
        return true;
    }
    return false;
}
template<class T, class F>
bool chmax(T &x, F y){
    if(x<y){
        x=y;
        return true;
    }
    return false;
}
double pass_time=0;
template<class monoid>
struct segtree{
    int n;
    vector<monoid>node;
    static monoid e(){
        return monoid::e();
    }
    static monoid op(monoid a,monoid b){
        return monoid::op(a,b);
    }

    segtree(){}
    segtree(int n):n(n),node(n*2,e()){
        assert(0<=n);
    }
    void set(int i,monoid x){
        assert(0<=i&&i<n);
        node[i+=n]=x;
        while(i>>=1)node[i]=op(node[i<<1],node[i<<1|1]);
    }
    monoid prod(int l,int r) const {
        assert(0<=l&&l<=r&&r<=n);
        l+=n,r+=n;
        monoid sml=e(),smr=e();
        while(l<r){
            if(l&1)sml=op(sml,node[l++]);
            if(r&1)smr=op(node[--r],smr);
            l>>=1,r>>=1;
        }
        return op(sml,smr);
    }
    monoid get(int i){
        assert(0<=i&&i<=n);
		return node[i+n];
	}
    //return max val s.t. f([L,val))) = true
    template<class F>
    int max_right(int L,const F&f) const {
        assert(f(e()));
        int l=n+L;   
        int w=1;
        monoid ansL=e();
        for(;L+w<=n;l>>=1,w<<=1){
            if(l&1){
                if(!(f(op(ansL,node[l]))))break;
                ansL=op(ansL,node[l++]);
                L+=w;
            }
        }
        while(l<<=1,w>>=1){
            if(L+w<=n&&f(op(ansL,node[l]))){
                ansL=op(ansL,node[l++]);
                L+=w;
            }
        }
        return L;
    }
    //return min val s.t. f([val,R)) = true
    template<class F>
    int min_left(int R,const F&f) const {
        assert(f(e()));
        int r=n+R;   
        int w=1;
        monoid ansR=e();
        for(;R-w>=n;r>>=1,w<<=1){
            if(r&1){
                if(!(f(op(ansR,node[r-1]))))break;
                ansR=op(ansR,node[--r]);
                R-=w;
            }
        }
        while(r<<=1,w>>=1){
            if(R-w>=n&&f(op(ansR,node[r-1]))){
                ansR=op(ansR,node[--r]);
                R-=w;
            }
        }
        return R;
    }
};
struct S{
    ll ma;
    ll sm;
    static S op(S a,S b){
        return S{max(a.ma,b.ma+a.sm),a.sm+b.sm};
    }
    static S e(){
        return {0,0};
    }
    static S add(S a,int b){
        return {a.ma+b,a.sm+b};
    }
};

int solve(int a,int b,int t,vc<int>x,vc<int>y,vc<int>w,vc<int>s){
    rep(i,a)x[i]--;
    rep(i,b)y[i]--;
    int TA,TB;
    {
        vc<int>compress;
        rep(i,t){
            compress.push_back(w[i]);
        }
        rep(i,a){
            compress.push_back(x[i]);
        }
        sort(all(compress));
        compress.erase(unique(all(compress)),compress.end());
        rep(i,t)w[i]=lower_bound(all(compress),w[i])-compress.begin();
        rep(i,a)x[i]=lower_bound(all(compress),x[i])-compress.begin();
        TA=compress.size()+1;
    
    }
    {
        vc<int>compress;
        rep(i,t){
            compress.push_back(s[i]);
        }
        rep(i,b){
            compress.push_back(y[i]);
        }
        sort(all(compress));
        compress.erase(unique(all(compress)),compress.end());
        rep(i,t)s[i]=lower_bound(all(compress),s[i])-compress.begin();
        rep(i,b)y[i]=lower_bound(all(compress),y[i])-compress.begin();
        TB=compress.size()+1;
    }
    vc<vc<array<int,2>>>query(TA);
    rep(i,t){
        query[w[i]].push_back({s[i],1});
    }
    rep(i,a){
        query[x[i]].push_back({-1,-1});
    }
    
    int ac=t+1,wa=0;
    while(ac-wa>1){
        int wj=ac+wa>>1;
        segtree<S>seg(TB);
        
        ll offset=0;
        rep(i,b){
            offset-=wj;
            //seg.set(0,S::add(seg.get(0),-wj));
            if(y[i]+1<TB)seg.set(y[i]+1,S::add(seg.get(y[i]+1),wj));
            //seg.apply(0,y[i]+1,-wj);
        }
        int ng=0;
        drep(i,TA){
            for(auto&[x,t]:query[i]){
                if(t==1){
                    offset++;
                    //seg.set(0,S::add(seg.get(0),1));
                    if(x+1<TB)seg.set(x+1,S::add(seg.get(x+1),-1));
                    //seg.apply(0,x+1,1);
                }else{
                    //seg.apply(0,TA,-wj);
                    offset-=wj;
                }
            }
            if(seg.prod(0,TB).ma+offset>0)ng=1;
        }
        if(!ng){
            ac=wj;
        }
        else wa=wj;
    }   
    if(ac==t+1)return -1;
    return ac;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    vc<int>x(A),y(B),w(T),s(T);
    rep(i,A)x[i]=X[i];
    rep(i,B)y[i]=Y[i];
    rep(i,T)w[i]=W[i];
    rep(i,T)s[i]=S[i];
    return solve(A,B,T,x,y,w,s);
}
namespace judge{
    void run(){
        int a,b,t;
        cin>>a>>b>>t;
        vc<int>x(a),y(b),w(t),s(t);
        rep(i,a)cin>>x[i];
        rep(i,b)cin>>y[i];
        rep(i,t)cin>>w[i]>>s[i];
        dbg(solve(a,b,t,x,y,w,s));
    }
};
//int main(){judge::run();}
//g++ robot/robots.cpp -D t9unkubj

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