Submission #582918

#	Time	Username	Problem	Language	Result	Execution time	Memory
582918		MohamedFaresNebili	Robots (IOI13_robots)	C++14	100 / 100	768 ms	21552 KiB

robots

#include <bits/stdc++.h>
#include "robots.h"
#include <ext/pb_ds/assoc_container.hpp>
 
        using namespace std;
        using namespace __gnu_pbds;
 
        using ll = long long;
        using pi = pair<ll, pair<ll, ll>>;
        using ii = pair<int, int>;
 
        #define pb push_back
        #define pp pop_back
        #define ff first
        #define ss second
        #define lb lower_bound
 
        typedef tree<int, null_type, less<int>, rb_tree_tag,
            tree_order_statistics_node_update> indexed_set;
 
       bool cmp(ii A, ii B) {
            if(max(A.ff, A.ss) != max(B.ff, B.ss))
                return max(A.ff, A.ss) > max(B.ff, B.ss);
            return min(A.ff, A.ss) > min(B.ff, B.ss);
        }
        bool comp(ii A, ii B) {
            if(A.ff != B.ff)
                return A.ff > B.ff;
            return A.ss > B.ss;
        }
 
        int st[400001], St[400001];
        void update(int v, int l, int r, int p) {
            if(l == r) {
                st[v]++;
                return;
            }
            int md = (l + r) / 2;
            if(p <= md)
                update(v * 2, l, md, p);
            else update(v * 2 + 1, md + 1, r, p);
            st[v] = min(st[v * 2], st[v * 2 + 1]);
        }
        void Update(int v, int l, int r, int p) {
            if(l == r) {
                St[v]++;
                return;
            }
            int md = (l + r) / 2;
            if(p <= md)
                Update(v * 2, l, md, p);
            else Update(v * 2 + 1, md + 1, r, p);
            St[v] = min(St[v * 2], St[v * 2 + 1]);
        }
        int query(int v, int l, int r, int lo, int hi) {
            if(l > hi || r < lo) return 1e9 + 7;
            if(l >= lo && r <= hi) return st[v];
            return min(query(v * 2, l, (l + r) / 2, lo, hi),
                       query(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi));
        }
        int Query(int v, int l, int r, int lo, int hi) {
            if(l > hi || r < lo) return 1e9 + 7;
            if(l >= lo && r <= hi) return St[v];
            return min(Query(v * 2, l, (l + r) / 2, lo, hi),
                       Query(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi));
        }
        int get(int v, int l, int r, int lo, int hi, int val) {
            if(l > hi || r < lo) return 1e9 + 7;
            if(l >= lo && r <= hi && l == r) {
                if(st[v] == val) return l;
                return 1e9 + 7;
            }
            if(l >= lo && r <= hi) {
                if(st[v * 2] <= val)
                    return get(v * 2, l, (l + r) / 2, lo, hi, val);
                if(st[v * 2 + 1] <= val)
                    return get(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, val);
                return 1e9 + 7;
            }
            int A = get(v * 2, l, (l + r) / 2, lo, hi, val);
            int B = get(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, val);
            return min(A, B);
        }
        int Get(int v, int l, int r, int lo, int hi, int val) {
            if(l > hi || r < lo) return 1e9 + 7;
            if(l >= lo && r <= hi && l == r) {
                if(St[v] == val) return l;
                return 1e9 + 7;
            }
            if(l >= lo && r <= hi) {
                if(St[v * 2] <= val)
                    return Get(v * 2, l, (l + r) / 2, lo, hi, val);
                if(St[v * 2 + 1] <= val)
                    return Get(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, val);
              	return 1e9 + 7;
            }
            int A = Get(v * 2, l, (l + r) / 2, lo, hi, val);
            int B = Get(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, val);
            return min(A, B);
        }
 
        int putaway(int A, int B, int T, int X[],
                    int Y[], int W[], int S[]) {
            vector<ii> arr;
            for(int l = 0; l < T; l++)
                arr.pb({W[l], S[l]});
            if(B > 0) sort(arr.begin(), arr.end(), cmp);
            else sort(arr.begin(), arr.end(), comp);
            sort(X, X + A), sort(Y, Y + B);
            for(int l = T - 1; l >= 0; l--) {
                int U = arr[l].ff, V = arr[l].ss;
                if(A > 0 && U < X[A - 1]) continue;
                if(B > 0 && V < Y[B - 1]) continue;
                return -1;
            }
            int occ[A + B];
            memset(occ, 0, sizeof occ);
            for(int l = 0; l < T; l++) {
                int U = arr[l].ff, V = arr[l].ss;
                int i = lb(X, X + A, U + 1) - X;
                int j = lb(Y, Y + B, V + 1) - Y;
 
                int x = query(1, 0, A - 1, i, A - 1);
                int y = Query(1, 0, B - 1, j, B - 1);
 
                int L = get(1, 0, A - 1, i, A - 1, x);
                int R = Get(1, 0, B - 1, j, B - 1, y) + A;
 
                if(i == A) {
                    occ[R]++; Update(1, 0, B - 1, R - A);
                    continue;
                }
                if(j == B) {
                    occ[L]++; update(1, 0, A - 1, L);
                    continue;
                }
                if(occ[R] < occ[L])
                    Update(1, 0, B - 1, R - A);
                else update(1, 0, A - 1, L);
                if(occ[R] < occ[L]) swap(L, R);
                occ[L]++;
            }
            int res = 0;
            for(int l = 0; l < A + B; l++) {
                res = max(res, occ[l]);
            }
            return res;
        }

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