Submission #1131836

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131836		t9unkubj	Robots (IOI13_robots)	C++20	76 / 100	3095 ms	36236 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 T,T (*op)(T, T),class F,T (*mapping)(T,F),F (*merge)(F, F)>
struct lazy_segtree{
    int n;
    vector<T>data;
    vector<F>lazy;
    int log;
    T e;
    F id;
    lazy_segtree(int n1,T e,F id):n(n1),e(e),id(id){
        int n_=1;
        log=0;
        while(n_<=n)n_*=2,log++;
        data=vector<T>(n_*2,e);
        lazy=vector<F>(n_,id);
        n=n_;
        for(int i=n_-1;i>0;i--)update(i);
    }
    void update(int k){
        data[k]=op(data[k*2],data[k*2+1]);
    }
    void apply(int k,F x){//
        data[k]=mapping(data[k],x);
        if(k<n){
            lazy[k]=merge(lazy[k],x);
            if(lazy[k]==id)return;
            //segment tree beats! if(data[k].fail)push(k),update(k);
        }
    }
    void push(int k){//上から遅延素を伝播させる
        apply(k*2,lazy[k]);
        apply(k*2+1,lazy[k]);
        lazy[k]=id;
    }
    void set(int p,T x){
        p+=n;
        for(int i=log;i>=1;i--){
            push(p>>i);
        }
        data[p]=x;
        for(int i=1;i<=log;i++){
            update(p>>i);
        }
    }
    void apply(int l,int r,F x){
        if(l==r)return;
        l+=n,r+=n;
        for(int i=log;i>=1;i--){
            if(((l>>i)<<i)!=l)push(l>>i);
            if(((r>>i)<<i)!=r)push((r-1)>>i);
        } 
        int l2{l},r2{r};
        while(l<r){
            if(l&1)apply(l++,x);
            if(r&1)apply(--r,x);
            l>>=1,r>>=1;
        }
        l=l2,r=r2;
        for(int i=1;i<=log;i++){
            if(((l>>i)<<i)!=l)update(l>>i);
            if(((r>>i)<<i)!=r)update((r-1)>>i);
        }
    }
    T prod(int l,int r){
        l+=n,r+=n;
        for(int i=log;i>=1;i--){
            if(((l>>i)<<i)!=l)push(l>>i);
            if(((r>>i)<<i)!=r)push((r-1)>>i);
        } 
        T sml=e,smr=e;
        while(l<r){
            if(l&1)sml=op(sml,data[l++]);
            if(r&1)smr=op(data[--r],smr);
            l>>=1,r>>=1;
        }
        return op(sml,smr);
    }
    T get(int p){
        p+=n;
        for(int i=log;i>=1;i--)push(p>>i);
        return data[p];
    }
};
int op(int a,int b){
    return max(a,b);
}
int ap(int a,int b){
    return a+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;
    {
        map<int,int>compress;
        rep(i,t){
            compress[w[i]]=0;
        }
        rep(i,a){
            compress[x[i]]=0;
        }
        int id=1;for(auto&[x,y]:compress)y=id++;
        rep(i,t)w[i]=compress[w[i]];
        rep(i,a)x[i]=compress[x[i]];
        TA=compress.size()+1;
    
    }
    {
        map<int,int>compress;
        rep(i,t){
            compress[s[i]]=0;
        }
        rep(i,b){
            compress[y[i]]=0;
        }
        int id=1;for(auto&[x,y]:compress)y=id++;
        rep(i,t)s[i]=compress[s[i]];
        rep(i,b)y[i]=compress[y[i]];
        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;
        lazy_segtree<int,op,int,ap,ap>seg(TB,-1e9,0);
        rep(i,TB)seg.set(i,0);
        rep(i,b){
            seg.apply(0,y[i]+1,-wj);
        }
        int ng=0;
        ll offset=0;
        drep(i,TA){
            for(auto&[x,t]:query[i]){
                if(t==1){
                    seg.apply(0,x+1,1);
                }else{
                    //seg.apply(0,TA,-wj);
                    offset+=wj;
                }
            }
            if(seg.prod(0,TB)-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: 0 / 14
• Subtask 3: 25 / 25
• Subtask 4: 37 / 37
• Subtask 5: 0 / 10