Submission #575312

#	Time	Username	Problem	Language	Result	Execution time	Memory
575312		nghiass001	Handcrafted Gift (IOI20_gift)	C++17	100 / 100	1186 ms	44364 KiB

gift

#include <bits/stdc++.h>
#define FOR(i,l,r) for(int i=(l); i<=(r); ++i)
#define REP(i,l,r) for(int i=(l); i<(r); ++i)
#define FORD(i,r,l) for(int i=(r); i>=(l); --i)
#define REPD(i,r,l) for(int i=(r)-1; i>=(l); --i)
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

template<class key, class value = null_type, class cmp = std::less<key>>
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

void craft(std::string &s);

int construct(int n, int r, vector<int> a, vector<int> b, vector<int> x) {
    ordered_set<int> ST;
    FOR(i, 0, n) ST.insert(i);
    REP(i, 0, r) if (x[i] == 1) {
        while (true) {
            auto pos = ST.upper_bound(a[i]);
            if (*pos <= b[i]) ST.erase(pos);
            else break;
        }
    }
    REP(i, 0, r) if (x[i] == 2) {
        if (ST.upper_bound(a[i]) == ST.upper_bound(b[i]))
            return 0;
    }

    string s;

    int tmp = 0;
    for(auto i2 = ST.begin(), i = i2++; i2 != ST.end(); i = i2++) {
        tmp ^= 1;
        char c = tmp ? 'R' : 'B';
        REP(j, *i, *i2) s += c;
    }
    craft(s);
    return 1;
}

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 25 / 25
• Subtask 5: 30 / 30