oj.uz

Submission #991058

# Submission time Handle Problem Language Result Execution time Memory
991058 2024-06-01T07:46:22 Z User0069 Teams (IOI15_teams) C++17
77 / 100
 4000 ms 383624 KB 
#include<bits/stdc++.h>
#include"teams.h"
#define taskname "vcl"
#define el '\n'
#define fi first
#define sc second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
//#define int ll
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
#define Faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int maxn=5e5+3;
const int mod=1e9+7;
const int INF=1e9+7;
int N;
struct node
{
    node *l,*r;
    int val;
    node():l(NULL),r(NULL),val(0){};
};
node* root[maxn];
vector<int> v[maxn];
node* cons(node* kk,int cl,int cr)
{
    kk=new node();
    if(cl==cr)
    {
        return kk;
    }
    int mid=(cl+cr)/2;
    kk->l=cons(kk->l,cl,mid);
    kk->r=cons(kk->r,mid+1,cr);
    return kk;
}
node* update(node* kk,int cl,int cr,int pos,int val)
{
    node* kkk=new node();
    kkk->l=kk->l;
    kkk->r=kk->r;
    kkk->val=kk->val;
    if(cl==cr)
    {
        kkk->val+=val;
        return kkk;
    }
    int mid=(cl+cr)/2;
    if(pos<=mid) kkk->l=update(kk->l,cl,mid,pos,val);
    else kkk->r=update(kk->r,mid+1,cr,pos,val);
    kkk->val=kkk->l->val+kkk->r->val;
    return kkk;
}
int get(node* kk,int cl,int cr,int l,int r )
{
    if(cl>r||cr<l) return 0;
    if(cl>=l&&cr<=r) return kk->val;
    int mid=(cl+cr)/2;
    return get(kk->l,cl,mid,l,r)+get(kk->r,mid+1,cr,l,r);
}
int cnt(int a,int b,int c,int d)
{
    return get(root[b],0,N,c,d)-((a>0)?get(root[a-1],0,N,c,d):0);
}
void init(int32_t n,int32_t* a,int32_t* b)
{
    N=n;
    root[0]=cons(root[0],0,n);
    for(int i=0;i<n;i++)
    {
        v[b[i]].push_back(a[i]);
    }
    for(int i=1;i<=n;i++)
    {
        root[i]=root[i-1];
        for(int x:v[i])
        {
            root[i]=update(root[i],0,n,x,1);
        }
    }
    root[n+1]=root[n];
}
struct ele
{
    int a,b,range,rmd;
};
int32_t can(int32_t m,int32_t* k)
{
    sort(k,k+m);
    vector<pii> v;
    int cur=k[0],num=1;
    for(int i=1;i<m;i++)
    {
        if(k[i]==cur)
        {
            num++;
        }
        else
        {
            v.push_back({cur,num});
            num=1;
            cur=k[i];
        }
    }
    v.push_back({cur,num});
    vector<ele> st;
    st.push_back({0,0,N,0});
    for(int i=0;i<v.size();i++)
    {
        int prev,late,a,b,sum=0;
        a=v[i].fi;
        prev=st.back().a;
        b=prev+1;
        late=(i==m-1)?N+1:v[i+1].fi;
        int ra=v[i].fi-1;
        int lmao=-1;
        while(st.back().range<=ra)
        {
            lmao=st.back().b;
            st.pop_back();
        }
        if(lmao!=-1) st.push_back({prev,lmao,ra,0});
//        for(ele w:st)
//        {
//            cout<<w.a<<" "<<w.b<<" "<<w.range<<" "<<w.rmd<<" ; ";
//        }
//        cout<<"\n";
        while(!st.empty()&&sum+(lmao=cnt(ra+1,st.back().range,b,v[i].fi))<v[i].fi*v[i].sc)
        {
            b=st.back().b;
            sum+=lmao+st.back().rmd;
            ra=st.back().range;
            st.pop_back();
        }
        if(st.empty()) return 0;
        int l=ra,r=st.back().range,ans=-1;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(sum+cnt(ra+1,mid,b,v[i].fi)>=v[i].fi*v[i].sc)
            {
                ans=mid;
                r=mid-1;
            }
            else l=mid+1;
        }
        st.push_back({a,b,ans,sum+cnt(ra+1,ans,b,v[i].fi)-v[i].fi*v[i].sc});
//        for(ele w:st)
//        {
//            cout<<w.a<<" "<<w.b<<" "<<w.range<<" "<<w.rmd<<" ; ";
//        }
//        cout<<"\n";
    }
    return 1;
}
//signed main()
//{
//    if (fopen(taskname".INP","r"))
//    {
//        freopen(taskname".INP","r",stdin);
//        freopen(taskname"1.OUT","w",stdout);
//    }
//    Faster
//    int n,q;
//    cin>>n>>q;
//    int32_t _a[n],_b[n];
//    for(int i=0;i<n;i++)
//    {
//        cin>>_a[i]>>_b[i];
//    }
//    init(n,_a,_b);
//    while(q--)
//    {
//        int32_t _m;
//        cin>>_m;
//        int32_t _k[_m];
//        for(int i=0;i<_m;i++)
//        {
//            cin>>_k[i];
//        }
//        cout<<can(_m,_k)<<"\n";
//    }
//}

Compilation message

teams.cpp: In function 'int32_t can(int32_t, int32_t*)':
teams.cpp:93:17: warning: declaration of 'v' shadows a global declaration [-Wshadow]
   93 |     vector<pii> v;
      |                 ^
teams.cpp:27:13: note: shadowed declaration is here
   27 | vector<int> v[maxn];
      |             ^
teams.cpp:111:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |     for(int i=0;i<v.size();i++)
      |                 ~^~~~~~~~~
teams.cpp:113:18: warning: variable 'late' set but not used [-Wunused-but-set-variable]
  113 |         int prev,late,a,b,sum=0;
      |                  ^~~~

Subtask #1
21.0 / 21.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 79184 KB Output is correct
2 Correct 106 ms 79184 KB Output is correct
3 Correct 86 ms 79188 KB Output is correct
4 Correct 88 ms 79432 KB Output is correct
5 Correct 61 ms 77800 KB Output is correct
6 Correct 64 ms 77908 KB Output is correct
7 Correct 65 ms 77904 KB Output is correct
8 Correct 58 ms 77836 KB Output is correct
9 Correct 58 ms 78660 KB Output is correct
10 Correct 56 ms 79304 KB Output is correct
11 Correct 58 ms 79232 KB Output is correct
12 Correct 57 ms 79244 KB Output is correct
13 Correct 86 ms 79052 KB Output is correct
14 Correct 79 ms 79820 KB Output is correct
15 Correct 86 ms 80188 KB Output is correct
16 Correct 77 ms 80108 KB Output is correct
17 Correct 65 ms 79624 KB Output is correct
18 Correct 77 ms 79400 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 79444 KB Output is correct
2 Correct 95 ms 79464 KB Output is correct
3 Correct 645 ms 82516 KB Output is correct
4 Correct 92 ms 79376 KB Output is correct
5 Correct 426 ms 78420 KB Output is correct
6 Correct 367 ms 78200 KB Output is correct
7 Correct 65 ms 78160 KB Output is correct
8 Correct 296 ms 78308 KB Output is correct
9 Correct 59 ms 78792 KB Output is correct
10 Correct 62 ms 79816 KB Output is correct
11 Correct 80 ms 79864 KB Output is correct
12 Correct 376 ms 80076 KB Output is correct
13 Correct 521 ms 80228 KB Output is correct
14 Correct 873 ms 82772 KB Output is correct
15 Correct 305 ms 81048 KB Output is correct
16 Correct 317 ms 81108 KB Output is correct
17 Correct 204 ms 80316 KB Output is correct
18 Correct 213 ms 80076 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 650 ms 373664 KB Output is correct
2 Correct 684 ms 377120 KB Output is correct
3 Correct 3001 ms 383624 KB Output is correct
4 Correct 696 ms 377220 KB Output is correct
5 Correct 1179 ms 369636 KB Output is correct
6 Correct 1139 ms 369492 KB Output is correct
7 Correct 393 ms 369696 KB Output is correct
8 Correct 961 ms 369660 KB Output is correct
9 Correct 342 ms 371656 KB Output is correct
10 Correct 342 ms 369960 KB Output is correct
11 Correct 508 ms 370628 KB Output is correct
12 Correct 1201 ms 371416 KB Output is correct
13 Correct 2152 ms 373652 KB Output is correct
14 Execution timed out 4059 ms 382552 KB Time limit exceeded
15 Halted 0 ms 0 KB -