Submission #793261

#	Time	Username	Problem	Language	Result	Execution time	Memory
793261		ln_e	Handcrafted Gift (IOI20_gift)	C++17	10 / 100	179 ms	28808 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,ll>p[500005];
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=b[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);
ll last=-1;
for(ll i=0;i<r;i++)
{
    if(x[i]==2){
        ll st=0;
        if(p[i].f-1>=0){
            st=cnt[p[i].f-1];
        }
        ll val=cnt[p[i].s]-st;
        if(val==p[i].s-p[i].f+1){
            return 0;
        }
        if(val==0&&p[i].f>last){
            ans[p[i].f]='R';
            last=p[i].f;
            if(val+1==p[i].s-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]++;
    }
}
for(ll i=0;i<r;i++)
{
    if(x[i]==1){
        ll st=0;
        if(a[i]-1>=0){
            st=cnt[a[i]-1];
        }
        if(cnt[b[i]]-st==0||cnt[b[i]]-st==b[i]-a[i]+1){
            continue;
        }
        return 0;
    }else {
    ll st=0;
        if(a[i]-1>=0){
            st=cnt[a[i]-1];
        }
        if(cnt[b[i]]-st==0||cnt[b[i]]-st==b[i]-a[i]+1){
            return 0;
        }
    }
}
craft(ans);
return 1;
}

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