Submission #793841

#	Time	Username	Problem	Language	Result	Execution time	Memory
793841		ln_e	Handcrafted Gift (IOI20_gift)	C++17	100 / 100	202 ms	40392 KiB

gift

#include <bits/stdc++.h> //Andrei Alexandru a.k.a Sho
#include "gift.h"
using ll=long long;
using ld=long double;
int const INF=1000000005;
ll const LINF=1000000000000000005;
ll const mod=6700417;
ld const PI=3.14159265359;
ll const MAX_N=3e5+5;
ld const EPS=0.00000001;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define endl '\n'
#define sz(a) (int)a.size()
#define CODE_START  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
ll pref[500005],cnt[500005];
pair<ll,pair<ll,ll>>p[500005];
bool cmp(pair<ll,pair<ll,ll>>x,pair<ll,pair<ll,ll>>y){
   if(x.s.f==y.s.f){
    return x.f<y.f;
   }else return x.s.f<y.s.f;
}
int construct(int n, int r, std::vector<int> a, std::vector<int> b, std::vector<int> x) {
 string ans="";   
for(ll i=0;i<n;i++)
{
    ans+='.';
}
for(ll i=0;i<r;i++){
    p[i].f=a[i];
    p[i].s.f=b[i];
    p[i].s.s=x[i];
   if(x[i]==1){
    pref[a[i]]++;
    pref[b[i]+1]--;
   }
}
for(ll i=0;i<n;i++){
    if(i-1>=0){
        pref[i]+=pref[i-1];
    }
    if(i-1>=0){
        cnt[i]=cnt[i-1];
    }
    if(pref[i]>=1){
        ans[i]='R';
        cnt[i]++;
    }else {
        ans[i]='B';
    }
}
sort(p,p+r,cmp);
ll last=-1;
for(ll i=0;i<r;i++)
{
    if(p[i].s.s==2){
        ll st=0;
        if(p[i].f-1>=0){
            st=cnt[p[i].f-1];
        }
        ll val=cnt[p[i].s.f]-st;
        if(val==p[i].s.f-p[i].f+1){
            return 0;
        }
        if(val==0&&p[i].f>last){
            ans[p[i].s.f]='R';
            last=p[i].s.f;
            if(val+1==p[i].s.f-p[i].f+1){
                return 0;
            }
        }

    }
}
cnt[0]=0;
for(ll i=0;i<n;i++){
    if(i-1>=0){
        cnt[i]=cnt[i-1];
    }
    if(ans[i]=='R'){
        cnt[i]++;
    }
}
craft(ans);
return 1;
}

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