oj.uz

Submission #1007504

# Submission time Handle Problem Language Result Execution time Memory
1007504 2024-06-25T04:34:58 Z bachhoangxuan Teams (IOI15_teams) C++17
100 / 100
 501 ms 171444 KB 
#include "teams.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5+5;
const int maxl = 25;
const int inf = 1e9;

int n;
int tree[maxn*maxl],lc[maxn*maxl],rc[maxn*maxl],T=1;
void build(int l,int r,int id){
    if(l==r) return;
    lc[id]=++T;rc[id]=++T;
    int mid=(l+r)>>1;
    build(l,mid,lc[id]);build(mid+1,r,rc[id]);
}
int update(int l,int r,int id,int p){
    if(l==r){
        tree[++T]=tree[id]+1;
        return T;
    }
    int mid=(l+r)>>1;
    int cc=++T;
    lc[cc]=lc[id];rc[cc]=rc[id];
    if(p<=mid) lc[cc]=update(l,mid,lc[id],p);
    else rc[cc]=update(mid+1,r,rc[id],p);
    tree[cc]=tree[lc[cc]]+tree[rc[cc]];
    return cc;
}
int query(int l,int r,int id,int tl,int tr){
    if(tr<l || r<tl) return 0;
    if(tl<=l && r<=tr) return tree[id];
    int mid=(l+r)>>1;
    return query(l,mid,lc[id],tl,tr)+query(mid+1,r,rc[id],tl,tr);
}
vector<int> e[maxn];
int root[maxn];

void init(int N, int A[], int B[]) {
    for(int i=0;i<N;i++) e[B[i]].push_back(A[i]);
    n=N;
    root[N+1]=1;
    build(1,N,1);
    for(int i=N;i>=1;i--){
        root[i]=root[i+1];
        for(int x:e[i]) root[i]=update(1,n,root[i],x);
    }
}

int cnt[maxn],dp[maxn];

int can(int M, int K[]) {
    vector<int> C;
    for(int i=0;i<M;i++){
        if(!cnt[K[i]]) C.push_back(K[i]);
        cnt[K[i]]+=K[i];
    }
    auto get = [&](int l,int r){
        l=(l==-1?0:C[l]);
        r=(r==-1?0:C[r]);
        return dp[l]+query(1,n,root[r],l+1,r)-cnt[r];
    };
    sort(C.begin(),C.end());
    vector<pair<int,int>> p;
    p.push_back({0,-1});
    int sz=(int)C.size();

    for(int i=0;i<sz;i++){
        /*
        int k=upper_bound(p.begin(),p.end(),make_pair(i,inf))-p.begin()-1;
        dp[C[i]]=get(p[k].second,i);
        if(dp[C[i]]<0){
            for(int x:C) cnt[x]=dp[x]=0;
            return 0;
        }
        while(!p.empty()){
            auto [x,j]=p.back();
            if(i<x && get(j,x)>=get(i,x)) p.pop_back();
            else break;
        }
        auto [l,j]=p.back();
        int r=sz;l++;
        while(l<r){
            int mid=(l+r)>>1;
            if(i<mid && get(j,mid)<=get(i,mid)) r=mid;
            else l=mid+1;
        }
        if(r<sz) p.push_back({r,i});
        */
        int x=C[i];
        dp[x]=inf;
        for(int j=max(-1,i-10);j<i;j++) dp[x]=min(dp[x],get(j,i));
        if(dp[x]<0){
            for(int x:C) cnt[x]=dp[x]=0;
            return 0;
        }
    }
    for(int x:C) cnt[x]=dp[x]=0;
    return 1;
}

Compilation message

teams.cpp: In function 'int can(int, int*)':
teams.cpp:93:21: warning: declaration of 'x' shadows a previous local [-Wshadow]
   93 |             for(int x:C) cnt[x]=dp[x]=0;
      |                     ^
teams.cpp:89:13: note: shadowed declaration is here
   89 |         int x=C[i];
      |             ^

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 18776 KB Output is correct
2 Correct 2 ms 18776 KB Output is correct
3 Correct 3 ms 18780 KB Output is correct
4 Correct 3 ms 18780 KB Output is correct
5 Correct 2 ms 18780 KB Output is correct
6 Correct 2 ms 18780 KB Output is correct
7 Correct 3 ms 18776 KB Output is correct
8 Correct 3 ms 18776 KB Output is correct
9 Correct 2 ms 18780 KB Output is correct
10 Correct 3 ms 18780 KB Output is correct
11 Correct 3 ms 18780 KB Output is correct
12 Correct 3 ms 18776 KB Output is correct
13 Correct 3 ms 18780 KB Output is correct
14 Correct 3 ms 18776 KB Output is correct
15 Correct 3 ms 18780 KB Output is correct
16 Correct 3 ms 18856 KB Output is correct
17 Correct 3 ms 18780 KB Output is correct
18 Correct 3 ms 18780 KB Output is correct
19 Correct 3 ms 18780 KB Output is correct
20 Correct 3 ms 18776 KB Output is correct
21 Correct 3 ms 18780 KB Output is correct
22 Correct 4 ms 18780 KB Output is correct
23 Correct 3 ms 18780 KB Output is correct
24 Correct 2 ms 18780 KB Output is correct
25 Correct 3 ms 18780 KB Output is correct
26 Correct 3 ms 18780 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 44968 KB Output is correct
2 Correct 32 ms 44948 KB Output is correct
3 Correct 32 ms 46992 KB Output is correct
4 Correct 33 ms 45224 KB Output is correct
5 Correct 18 ms 43868 KB Output is correct
6 Correct 18 ms 43868 KB Output is correct
7 Correct 21 ms 43884 KB Output is correct
8 Correct 17 ms 44636 KB Output is correct
9 Correct 17 ms 44500 KB Output is correct
10 Correct 16 ms 44084 KB Output is correct
11 Correct 17 ms 44244 KB Output is correct
12 Correct 18 ms 44236 KB Output is correct
13 Correct 24 ms 44500 KB Output is correct
14 Correct 25 ms 47200 KB Output is correct
15 Correct 33 ms 45908 KB Output is correct
16 Correct 32 ms 45904 KB Output is correct
17 Correct 20 ms 44892 KB Output is correct
18 Correct 20 ms 44644 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 45136 KB Output is correct
2 Correct 38 ms 45140 KB Output is correct
3 Correct 78 ms 50260 KB Output is correct
4 Correct 32 ms 45200 KB Output is correct
5 Correct 107 ms 44112 KB Output is correct
6 Correct 101 ms 44116 KB Output is correct
7 Correct 23 ms 44124 KB Output is correct
8 Correct 84 ms 45392 KB Output is correct
9 Correct 17 ms 44384 KB Output is correct
10 Correct 17 ms 44492 KB Output is correct
11 Correct 22 ms 44744 KB Output is correct
12 Correct 108 ms 45004 KB Output is correct
13 Correct 135 ms 45468 KB Output is correct
14 Correct 89 ms 49036 KB Output is correct
15 Correct 72 ms 46844 KB Output is correct
16 Correct 69 ms 46672 KB Output is correct
17 Correct 58 ms 45396 KB Output is correct
18 Correct 49 ms 45516 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 159824 KB Output is correct
2 Correct 267 ms 159656 KB Output is correct
3 Correct 449 ms 167764 KB Output is correct
4 Correct 260 ms 159828 KB Output is correct
5 Correct 272 ms 153684 KB Output is correct
6 Correct 248 ms 153680 KB Output is correct
7 Correct 95 ms 153752 KB Output is correct
8 Correct 224 ms 158548 KB Output is correct
9 Correct 99 ms 157380 KB Output is correct
10 Correct 77 ms 155588 KB Output is correct
11 Correct 123 ms 156352 KB Output is correct
12 Correct 330 ms 157120 KB Output is correct
13 Correct 437 ms 160196 KB Output is correct
14 Correct 501 ms 171444 KB Output is correct
15 Correct 305 ms 165584 KB Output is correct
16 Correct 322 ms 165592 KB Output is correct
17 Correct 184 ms 159864 KB Output is correct
18 Correct 179 ms 159860 KB Output is correct