oj.uz

Submission #745670

# Submission time Handle Problem Language Result Execution time Memory
745670 2023-05-20T21:08:44 Z ogibogi2004 Teams (IOI15_teams) C++14
77 / 100
 1034 ms 362692 KB 
#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN=5e5+6;
int n;
int a[MAXN];
int b[MAXN];
struct node
{
    int val;
    node *l, *r;
    node(int x){
        val=x;
        l=nullptr;
        r=nullptr;
    }
    node(node *_l,node *_r)
    {
        l=_l;
        r=_r;
        val=0;
        if(l)val+=l->val;
        if(r)val+=r->val;
    }
    node(node *t)
    {
        val=t->val;
        l=t->l;
        r=t->r;
    }
};
node *update(node *t,int val,int pos,int l=1,int r=n)
{
    //cerr<<"update "<<l<<" "<<r<<endl;
    if(l==r)return new node(val);
    int mid=(l+r)/2;
    if(pos>mid)
    {
        if(t==nullptr)return new node(nullptr, update(nullptr,val,pos, mid+1,r));
        else return new node(t->l, update(t->r,val,pos, mid+1,r));
    }
    else
    {
        if(t==nullptr)return new node(update(nullptr,val,pos,l,mid), nullptr);
        else return new node(update(t->l,val,pos,l,mid), t->r);
    }
}
int query(node *t,int ql,int qr,int l=1,int r=n)
{
    //cerr<<"query "<<l<<" "<<r<<" "<<ql<<" "<<qr<<endl;
    if(ql>r)return 0;
    if(t==nullptr)return 0;
    if(qr<l)return 0;
    if(l>=ql&&r<=qr)return t->val;
    int mid=(l+r)/2;
    return query(t->l,ql,qr,l,mid)+query(t->r,ql,qr,mid+1,r);
}
node *roots[MAXN];
struct segment
{
    int l,r;
};
vector<segment>v;
bool cmp(segment s1,segment s2)
{
    if(s1.r!=s2.r)return s1.r<s2.r;
    else return s1.l<s2.l;
}
vector<segment>s1[MAXN];
int sum[MAXN];
void init(int N, int A[], int B[]) {
    n=N;
    for(int i=0;i<N;i++)
    {
        a[i]=A[i];
        b[i]=B[i];
        v.push_back({A[i],B[i]});
    }
    sort(v.rbegin(),v.rend(),cmp);
    for(auto xd:v)
    {
        s1[xd.r].push_back(xd);
    }
    roots[n+1]=nullptr;
    for(int i=n;i>=1;i--)
    {
        roots[i]=roots[i+1];
        //cout<<"???\n";
        {
            for(auto xd:s1[i])
            {
                ++sum[xd.l];
                roots[i]=update(roots[i],sum[xd.l],xd.l,1,n);
                //cerr<<" "<<xd.l<<" ^^"<<endl;
            }
        }
    }
}
int m;
int k[MAXN];
int dp[MAXN];
int get_value1(int x)
{
    node* root_we_need = roots[x];
    return query(root_we_need,1,x,1,n);
}
int get_value(int i1,int i2)
{
    if(k[i1]+1>k[i2])return 0;
    //should return no. of segments with k[i2]>=l>k[i1] and r>=k[i2]
    //persistent segment tree can do :(
    node *root_we_need = roots[k[i2]];
    return query(root_we_need, k[i1]+1,k[i2],1,n);
}
int can(int M, int K[]) {
    //cerr<<"========query=========";
    sort(K,K+M);
    int sumk=0;
    for(int i=0;i<M;i++)
    {
        k[i]=K[i];
        sumk+=k[i];
    }
    if(sumk>n)return 0;
    m=M;
    dp[0]=get_value1(K[0])-K[0];
    if(dp[0]<0)return 0;
    vector<int>ids;
    ids.push_back(0);
    //cerr<<"0 : "<<dp[0]<<endl;
    for(int i=1;i<m;i++)
    {
        while(ids.size()>1)
        {
            int id1=ids[ids.size()-2];
            int id2=ids[ids.size()-1];
            if(get_value(id1, i)+dp[id1]<=get_value(id2, i)+dp[id2])
            {
                ids.pop_back();
            }
            else
            {
                break;
            }
        }
        dp[i]=min(dp[ids.back()]+get_value(ids.back(), i)-K[i],get_value1(K[i])-K[i]);
        //cerr<<i<<" : "<<dp[i]<<endl;
        if(dp[i]<0)return 0;
        ids.push_back(i);
    }
    return 1;
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 8 ms 11988 KB Output is correct
3 Correct 7 ms 12008 KB Output is correct
4 Correct 7 ms 12116 KB Output is correct
5 Correct 6 ms 12116 KB Output is correct
6 Correct 7 ms 12116 KB Output is correct
7 Correct 6 ms 12116 KB Output is correct
8 Correct 6 ms 12116 KB Output is correct
9 Correct 6 ms 12116 KB Output is correct
10 Correct 6 ms 12120 KB Output is correct
11 Correct 6 ms 12116 KB Output is correct
12 Correct 7 ms 12116 KB Output is correct
13 Correct 7 ms 12124 KB Output is correct
14 Correct 7 ms 12116 KB Output is correct
15 Correct 7 ms 12116 KB Output is correct
16 Correct 8 ms 12132 KB Output is correct
17 Correct 8 ms 11988 KB Output is correct
18 Correct 7 ms 11988 KB Output is correct
19 Correct 7 ms 12036 KB Output is correct
20 Correct 6 ms 11988 KB Output is correct
21 Correct 7 ms 11988 KB Output is correct
22 Correct 7 ms 12056 KB Output is correct
23 Correct 6 ms 11988 KB Output is correct
24 Correct 6 ms 12100 KB Output is correct
25 Correct 6 ms 11988 KB Output is correct
26 Correct 7 ms 11988 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 72904 KB Output is correct
2 Correct 115 ms 72936 KB Output is correct
3 Correct 119 ms 72940 KB Output is correct
4 Correct 124 ms 73736 KB Output is correct
5 Correct 79 ms 71640 KB Output is correct
6 Correct 79 ms 71632 KB Output is correct
7 Correct 83 ms 71712 KB Output is correct
8 Correct 82 ms 71680 KB Output is correct
9 Correct 81 ms 73116 KB Output is correct
10 Correct 82 ms 72676 KB Output is correct
11 Correct 74 ms 72372 KB Output is correct
12 Correct 74 ms 72256 KB Output is correct
13 Correct 83 ms 71904 KB Output is correct
14 Correct 85 ms 72840 KB Output is correct
15 Correct 110 ms 72740 KB Output is correct
16 Correct 105 ms 72868 KB Output is correct
17 Correct 81 ms 72668 KB Output is correct
18 Correct 90 ms 72696 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 73356 KB Output is correct
2 Correct 120 ms 73272 KB Output is correct
3 Correct 182 ms 76236 KB Output is correct
4 Correct 117 ms 73696 KB Output is correct
5 Correct 134 ms 72020 KB Output is correct
6 Correct 121 ms 72020 KB Output is correct
7 Correct 85 ms 72120 KB Output is correct
8 Correct 135 ms 72020 KB Output is correct
9 Correct 80 ms 73056 KB Output is correct
10 Correct 84 ms 73056 KB Output is correct
11 Correct 97 ms 72756 KB Output is correct
12 Correct 126 ms 72660 KB Output is correct
13 Correct 168 ms 72364 KB Output is correct
14 Correct 225 ms 76512 KB Output is correct
15 Correct 151 ms 74712 KB Output is correct
16 Correct 142 ms 74772 KB Output is correct
17 Correct 132 ms 74524 KB Output is correct
18 Correct 119 ms 74560 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 761 ms 352696 KB Output is correct
2 Correct 792 ms 352708 KB Output is correct
3 Correct 1034 ms 358568 KB Output is correct
4 Correct 739 ms 353396 KB Output is correct
5 Correct 511 ms 346084 KB Output is correct
6 Correct 535 ms 346140 KB Output is correct
7 Correct 439 ms 346164 KB Output is correct
8 Correct 528 ms 346104 KB Output is correct
9 Correct 397 ms 348344 KB Output is correct
10 Correct 400 ms 345772 KB Output is correct
11 Correct 439 ms 345464 KB Output is correct
12 Correct 533 ms 345512 KB Output is correct
13 Correct 721 ms 346020 KB Output is correct
14 Correct 1014 ms 362692 KB Output is correct
15 Correct 732 ms 358600 KB Output is correct
16 Incorrect 721 ms 358668 KB Output isn't correct
17 Halted 0 ms 0 KB -