Submission #1172806

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172806		adkjt	Handcrafted Gift (IOI20_gift)	C++20	15 / 100	72 ms	13128 KiB

gift

#include "gift.h"
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define f first
#define se second
set<pii> s;
/*10 3
2 4 1
6 8 1
4 6 1
*/
//int change[555555];
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)
        {
            int newl=a[i],newr=b[i];
            auto it=s.upper_bound({a[i]+1,a[i]});
            auto er=it;

            //cout<<(*s.begin()).f<<'\n';
            if(it!=s.begin())
            {
               it--;

               if((*it).se>=a[i]) {
                   //cout<<"W";
                newl=(*it).f;
               er=it;
               it++;
               s.erase(er);
               }
               else it++;
            }
//cout<<(*it).f<<' '<<(*it).se<<' ';
            while(it!=s.end()&&(*it).f<=b[i])
            {
                if((*it).se>b[i]) {
                    newr=(*it).se;
                }
                er=it;
                it++;
                s.erase(er);
            }
            //cout<<newl<<' '<<newr<<'\n';
            s.insert({newl,newr});
        }
    }
    for(int i=0;i<r;i++)
    {
        if(x[i]==2)
        {
            if(b[i]-a[i]==0)
                return 0;
            auto it=s.upper_bound({a[i]+1,n});
            //cout<<a[i]<<' '<<b[i]<<' '<<(*it).f<<' '<<(*it).se<<'\n';
            if(it!=s.begin())
            {
                it--;

                if(a[i]>=(*it).f&&b[i]<=(*it).se)
                    return 0;
            }


        }
    }
    string ans(n,'R');
    char color[]={'R','B'};
    int now=0,l=0;
    for(auto it=s.begin();it!=s.end();it++)
    {
        //cout<<(*it).f<<' '<<(*it).se<<'\n';
        for(int i=l;i<(*it).f;i++){
            now=(now+1)%2;
            ans[i]=color[now];
        }
        now=(now+1)%2;
        for(int i=(*it).f;i<=(*it).se;i++)
        {
            ans[i]=color[now];
        }
        l=(*it).se+1;
    }
    for(int i=l;i<n;i++){
            now=(now+1)%2;
            ans[i]=color[now];
    }

    craft(ans);
    return 1;
}

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