Submission #1228748

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228748		12345678	Handcrafted Gift (IOI20_gift)	C++20	100 / 100	147 ms	18940 KiB

gift

#include "gift.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=5e5+5;

int qs[nx], lst;
string s;
vector<pair<int, int>> rng;

int construct(int n, int r, std::vector<int> a, std::vector<int> b, std::vector<int> x) {
    for (int i=0; i<r; i++) if (x[i]==1) qs[a[i]]++, qs[b[i]]--;
    for (int i=0; i<n; i++)
    {
        qs[i+1]+=qs[i];
        if (!qs[i]) rng.push_back({lst, i}), lst=i+1;
    }
    for (int i=0; i<r; i++)
    {
        if (x[i]==2)
        {
            auto itr=upper_bound(rng.begin(), rng.end(), make_pair(b[i], INT_MAX));
            if (prev(itr)->first<=a[i]) return 0;
        }
    }
    s.resize(n, 'R');
    for (int i=0; i<rng.size(); i+=2) for (int j=rng[i].first; j<=rng[i].second; j++) s[j]='B';
    craft(s);
    return 1;
}

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