Submission #1189488

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189488		simona1230	Teams (IOI15_teams)	C++20	0 / 100	4094 ms	589824 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn=500005;

//static FILE *_inputFile, *_outputFile;
struct node
{
    int x,l,r;
    node(){}
    node(int _x,int _l,int _r)
    {
        x=_x;
        l=_l;
        r=_r;
    }
};

struct st
{
    vector<node> t={{0,-1,-1}};
    st(){}
    void add_l(int i)
    {
        if(t[i].l!=-1)return;
        t[i].l=t.size();
        t.push_back({0,-1,-1});
    }

    void add_r(int i)
    {
        if(t[i].r!=-1)return;
        t[i].r=t.size();
        t.push_back({0,-1,-1});
    }

    void update(int i,int l,int r,int id)
    {
        if(l==r)
        {
            t[i].x+=1;
            return;
        }

        int m=(l+r)/2;
        if(id<=m)
        {
            add_l(i);
            update(t[i].l,l,m,id);
        }
        else
        {
            add_r(i);
            update(t[i].r,m+1,r,id);
        }

        t[i].x=0;
        if(t[i].l!=-1)t[i].x+=t[t[i].l].x;
        if(t[i].r!=-1)t[i].x+=t[t[i].r].x;
    }

    int query(int i,int l,int r,int ql,int qr)
    {
        if(i==-1||ql>qr)return 0;
        if(ql<=l&&r<=qr)return t[i].x;
        int m=(l+r)/2;
        return query(t[i].l,l,m,ql,min(qr,m))+query(t[i].r,m+1,r,max(m+1,ql),qr);
    }
};

struct node2
{
    st x;
    int l,r;
    node2(){}
    node2(st _x,int _l,int _r)
    {
        x=_x;
        l=_l;
        r=_r;
    }
};

st h;
struct s2d
{
    vector<node2> t={{h,-1,-1}};
    s2d(){}

    void add_l(int i)
    {
        if(t[i].l!=-1)return;
        t[i].l=t.size();
        t.push_back({h,-1,-1});
    }

    void add_r(int i)
    {
        if(t[i].r!=-1)return;
        t[i].r=t.size();
        t.push_back({h,-1,-1});
    }

    void update(int i,int l,int r,int i1,int i2)
    {
        if(l==r)
        {
            t[i].x.update(0,1,maxn,i2);
            return;
        }

        int m=(l+r)/2;
        if(i1<=m)
        {
            add_l(i);
            update(t[i].l,l,m,i1,i2);
        }
        else
        {
            add_r(i);
            update(t[i].r,m+1,r,i1,i2);
        }

        if(t[i].l==-1)t[i].x=t[t[i].r].x;
        else if(t[i].r==-1)t[i].x=t[t[i].l].x;
        else t[i].x.update(0,1,maxn,i2);
    }

    int query(int i,int l,int r,int l1,int r1,int l2,int r2)
    {
        if(i==-1||l1>r1)return 0;
        if(l1<=l&&r<=r1)return t[i].x.query(0,1,maxn,l2,r2);
        int m=(l+r)/2;
        return query(t[i].l,l,m,l1,min(r1,m),l2,r2)+query(t[i].r,m+1,r,max(m+1,l1),r1,l2,r2);
    }
};

s2d t;

int n;
void init(int N, int A[], int B[])
{
    n=N;
    for(int i=0;i<N;i++)
        t.update(0,1,maxn,A[i],B[i]);
    //fprintf(_outputFile,"%d ", t.query(0,1,maxn,1,3,3,5));
}

int dp[maxn];
int can(int M, int k[])
{
    int answer=0;
    stack<pair<int,int> > s;
    for(int i=0;i<M;i++)
    {
        while(s.size()&&s.top().second==i)s.pop();
        int v1=t.query(0,1,maxn,1,k[i],k[i],maxn)-k[i];
        //fprintf(_outputFile,"%d ", v1);
        if(s.size()==0/*||dp[s.top().first]>=v1*/)
        {
            dp[i]=v1;
            while(s.size())s.pop();
            s.push({i,M});
            answer=min(answer,dp[i]);
            continue;
        }

        int j=s.top().first;
        dp[i]=dp[j]+t.query(0,1,maxn,k[j]+1,k[i],k[i],maxn)-k[i];
        int ans=M;
        int l=i+1,r=M-1;
        while(l<=r)
        {
            int m=(l+r)/2;
            if(dp[i]+t.query(0,1,maxn,k[i]+1,k[m],k[m],maxn)>=dp[j]+t.query(0,1,maxn,k[j]+1,k[m],k[m],maxn))
            {
                ans=m;
                r=m-1;
            }
            else l=m+1;
        }
        answer=min(answer,dp[i]);

        s.push({i,ans});
    }

    /*for(int i=0;i<M;i++)
    {
        fprintf(_outputFile,"%d ", dp[i]);
    }*/

    if(answer<0)return 0;
    return 1;
}

/*
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        cin>>x>>y;
        t.update(0,1,maxn,x,y);
    }

    int q;
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        int x,y,xx,yy;
        cin>>x>>y>>xx>>yy;
        cout<<t.query(0,1,maxn,x,y,xx,yy)<<endl;
    }
    return 0;
}
*/

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