oj.uz

Submission #991018

# Submission time Handle Problem Language Result Execution time Memory
991018 2024-06-01T04:26:18 Z User0069 Teams (IOI15_teams) C++17
0 / 100
 2689 ms 524292 KB 
#include<bits/stdc++.h>
#include<teams.h>
#define taskname ""
#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)-get(root[a-1],0,N,c,d);
}
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<int> v;
    vector<ele> st;
    st.push_back({0,0,N,0});
    for(int i=0;i<m;i++)
    {
        int prev,a,b,sum=0;
        a=k[i];
        prev=st.back().a;
        b=prev+1;
        int ra=k[i]-1;
        int lmao;
        while(!st.empty()&&sum+(lmao=cnt(ra+1,st.back().range,b,k[i]))+st.back().rmd<k[i])
        {
            b=st.back().b;
            sum+=lmao;
            ra=st.back().range;
            st.pop_back();
        }
        if(st.empty()) return 0;
        int l=ra+1,r=st.back().range,ans=-1;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(sum+cnt(ra+1,mid,b,k[i])>=k[i])
            {
                ans=mid;
                r=mid-1;
            }
            else l=mid+1;
        }
        st.push_back({a,b,ans,sum+cnt(ra+1,ans,b,k[i])-k[i]});
    }
    return 1;
}
//signed main()
//{
//    if (fopen(taskname".INP","r"))
//    {
//        freopen(taskname".INP","r",stdin);
//        freopen(taskname".OUT","w",stdout);
//    }
//    Faster
//    int n,q;
//    cin>>n>>q;
//    int32_t _a[n],_b[n];
//    for(int i=1;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<int> v;
      |                 ^
teams.cpp:27:13: note: shadowed declaration is here
   27 | vector<int> v[maxn];
      |             ^

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 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 12888 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 3 ms 12892 KB Output is correct
9 Correct 3 ms 13144 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Runtime error 10 ms 25948 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 79436 KB Output is correct
2 Correct 89 ms 79096 KB Output is correct
3 Correct 86 ms 79188 KB Output is correct
4 Correct 93 ms 79444 KB Output is correct
5 Correct 62 ms 77748 KB Output is correct
6 Correct 60 ms 77904 KB Output is correct
7 Correct 86 ms 77908 KB Output is correct
8 Correct 59 ms 77904 KB Output is correct
9 Runtime error 112 ms 159436 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 79516 KB Output is correct
2 Correct 104 ms 79636 KB Output is correct
3 Correct 602 ms 82300 KB Output is correct
4 Correct 87 ms 79440 KB Output is correct
5 Correct 382 ms 78252 KB Output is correct
6 Correct 348 ms 78288 KB Output is correct
7 Correct 64 ms 78164 KB Output is correct
8 Correct 279 ms 78164 KB Output is correct
9 Runtime error 114 ms 159432 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 618 ms 373328 KB Output is correct
2 Correct 613 ms 373332 KB Output is correct
3 Correct 2689 ms 379156 KB Output is correct
4 Correct 590 ms 373360 KB Output is correct
5 Correct 1134 ms 366932 KB Output is correct
6 Correct 1043 ms 367076 KB Output is correct
7 Correct 309 ms 366928 KB Output is correct
8 Correct 884 ms 366932 KB Output is correct
9 Runtime error 2514 ms 524292 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -