Submission #70713

#	Time	Username	Problem	Language	Result	Execution time	Memory
70713		mr_banana	Teams (IOI15_teams)	C++17	0 / 100	4061 ms	78952 KiB

teams

#include "teams.h"
#include<bits/stdc++.h>
using namespace std;
const int MN=5e5+100;
vector<int> seg[4*MN];
int n;
/*void add(int p,int x,int v=1,int s=0,int e=n){
    if(e-s<2){
        seg[v].push_back(x);
        return;
    }
    int mid=(s+e)/2;
    if(p<mid){
        add(p,x,2*v,s,mid);
    }
    else{
        add(p,x,2*v+1,mid,e);
    }
}
void build(int v=1,int s=0,int e=n){
    if(e-s<2){
        sort(seg[v].begin(),seg[v].end());
        return;
    }
    int mid=(s+e)/2;
    build(2*v,s,mid);
    build(2*v+1,mid,e);
    merge(seg[2*v].begin(),seg[2*v].end(),seg[2*v+1].begin(),seg[2*v+1].end(),seg[v].begin());
}
int query(int l,int r,int x,int v=1,int s=0,int e=n){
    if(l<=s && e<=r){
        return upper_bound(seg[v].begin(),seg[v].end(),x)-seg[v].begin();
    }
    if(l>=e || s>=r){
        return 0;
    }
    int mid=(s+e)/2;
    return query(l,r,x,2*v,s,mid)+query(l,r,x,2*v+1,mid,e);
}
int query2(int l,int r,int x,int y){
    return query(l,r,y)-query(l,r,x);
}*/
int a1[MN],b1[MN];
void init(int N, int a[], int b[]) {
    n=N;
    for(int i=0;i<n;i++){
        a1[i]=--a[i];
        b1[i]=--b[i];
        //add(a[i],b[i]);
    }
    //build();
}
int num[MN];
int meg[MN];
int can(int m, int k[]) {
    sort(k,k+m);
    int p1=0;
    for(int i=0;i<m;i++){
        k[i]--;
        if(i>0 && k[i]!=k[i-1]){
            p1++;
            num[p1]=0;
            meg[p1]=k[i];
        }

        num[p1]++;
    }
    p1++;
    long long mx=0;
    for(int i=0;i<p1;i++){
        int cnt1=0,cnt2=0,cnt3=0;
        for(int j=0;j<n;j++){
            //cout<<a1[j]<<" "<<b1[j]<<endl;
            if(a1[j]<=meg[i] && b1[j]>=meg[i]){
                cnt1++;
                if((i==0 || a1[j]>meg[i-1])){
                    cnt2++;
                    if(i+1==p1 || b1[j]<meg[i+1]){
                        cnt3++;
                    }
                }
            }
        }
      //  cout<<i<<" "<<cnt1<<" "<<cnt2<<" "<<cnt3<<endl;
        if(cnt3<1ll*(meg[i]+1)*num[i]){
            mx=min(mx+cnt2,1ll*cnt1)-1ll*num[i]*(meg[i]+1);
        }
        if(mx<0){
            return 0;
        }
    }
	return 1;
}

• Subtask 1: 0 / 21
• Subtask 2: 0 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23