Submission #765905

#	Time	Username	Problem	Language	Result	Execution time	Memory
765905		fatemetmhr	Robots (IOI13_robots)	C++17	100 / 100	2548 ms	30628 KiB

robots

//  ~ Be Name Khoda ~  //
 
#include "robots.h"
#include <bits/stdc++.h>
 
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")
 
using namespace std;
 
typedef long long ll;
 
#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
 
const int maxn  =  1e6   + 10;
const int maxn5 =  1e6   + 10;
const int maxnt =  3e5   + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   + 7;
const ll  inf   =  1e18;
 
bool mark[maxn5];
 
int n, m, t;
priority_queue <pair<int, int>> have[2];
int pt[2], ind[2];
pair <int, int> av[2][maxn5];

struct __seg{
    ll mn[maxnt], lazy[maxnt];

    void add(int lq, int rq, int val, int v, int l = 0, int r = max(n, m) + 1){
        if(rq <= l || r <= lq)
            return;
        if(lq <= l && r <= rq){
            lazy[v] += val;
            mn[v] += val;
            return;
        }
        int mid = (l + r) >> 1;
        add(lq, rq, val, v * 2, l, mid);
        add(lq, rq, val, v * 2 + 1, mid, r);
        mn[v] = min(mn[v * 2], mn[v * 2 + 1]) + lazy[v];
    }

    void build(int l, int r, ll val, int v){
        if(r - l == 1){
            mn[v] = val * l;
            ////cout << "hmmm " << v << ' ' << mn[v] << endl;
            return;
        }
        int mid = (l + r) >> 1;
        build(l, mid, val, v * 2);
        build(mid, r, val, v * 2 + 1);
        mn[v] = min(mn[v * 2], mn[v * 2 + 1]);
    }

    inline void clear(ll val){
        memset(lazy, 0, sizeof lazy);
        build(0, max(n, m) + 1, val, 1);
        ////cout << "hmmm " << mn[1] << ' ' << n << ' ' << m << endl;
    }
} seg[2];
 
inline bool addone(int id, ll lim, int m, int *s){
    //cout << "here we have " << id << ' ' << lim  << ' ' << av[id][ind[id]].fi << ' ' << max(n, m) << endl;
    //cout << seg[id].mn[1] << endl;
    seg[id].add(av[id][ind[id]].fi, max(n, ::m) + 1, -1, 1);
    bool check = seg[id].mn[1] >= 0;
    //cout << "ok " << check << ' ' << have[id].size() << endl;
    if(!check){
        int val = have[id].top().fi, v = have[id].top().se;
        ////cout << "it's " << val << ' ' << v << ' ' << s[av[id][ind[id]].se] << ' ' << av[id][ind[id]].se << endl;
        if(m - s[av[id][ind[id]].se] >= val){
            //////cout << "ha? " << endl;
            val = m - s[av[id][ind[id]].se];
            v = av[id][ind[id]].fi;
            seg[id ^ 1].add(val, max(n, ::m) + 1, -1, 1);
            if(seg[id ^ 1].mn[1] < 0)
                return false;
            seg[id].add(v, max(n, ::m) + 1, 1, 1);
            ind[id]++;
            return true;
        }
        have[id].pop();
        seg[id ^ 1].add(val, max(n, ::m) + 1, -1, 1);
        if(seg[id ^ 1].mn[1] < 0)
                return false;
        seg[id].add(v, max(n, ::m) + 1, 1, 1);
    }
    have[id].push({m - s[av[id][ind[id]].se], av[id][ind[id]].fi});
    ind[id]++;
    return true;
}
 
inline bool check(ll lim, int *x, int *y, int *w, int *s){
    //cout << "checkkkkkkkkkkkkkkkkk " << lim  << endl;
    seg[0].clear(lim);
    seg[1].clear(lim);
    ind[0] = ind[1] = 0;
    while(have[0].size())
        have[0].pop();
    while(have[1].size())
        have[1].pop();
    while(ind[0] < pt[0] || ind[1] < pt[1]){
        ////cout << "here " << ind[0] << ' ' << pt[0] << ' ' << ind[1] << ' ' << pt[1] << endl;
        if(ind[0] < pt[0] && (ind[1] == pt[1] || av[0][ind[0]].fi < av[1][ind[1]].fi)){
            ////cout << "etering for " << 0 << endl;
            if(!addone(0, lim, m, s))
                return false;
        }
        else{
            ////cout << "entering for " << 1 << endl;
            if(!addone(1, lim, n, w))
                return false;
        }
    }
    return true;
}
 
int putaway(int a, int b, int T, int x[], int y[], int w[], int s[]) {
    n = a;
    m = b;
    t = T;
    sort(x, x + n);
    sort(y, y + m);
    for(int i = 0; i < t; i++){
        if(w[i] >= x[n - 1] && s[i] >= y[m - 1])
            return -1;
        w[i] = upper_bound(x, x + n, w[i]) - x;
        s[i] = upper_bound(y, y + m, s[i]) - y;
    }
    pt[0] = pt[1] = 0;
    for(int i = 0; i < t; i++){
        //////cout << "hen? " << i << ' ' << w[i] << ' ' << n - w[i] << endl;
        av[n - w[i] < m - s[i]][pt[n - w[i] < m - s[i]]++] = {max(n - w[i], m - s[i]), i};
    }
    sort(av[0], av[0] + pt[0]);
    sort(av[1], av[1] + pt[1]);
    ////cout << n << ' ' << m << endl;
    int lo = 0, hi = t;
    while(hi - lo > 1){
        int mid = (hi + lo) >> 1;
        if(check(mid, x, y, w, s))
            hi = mid;
        else
            lo = mid;
    }
    return hi;
}

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