oj.uz

Submission #991069

# Submission time Handle Problem Language Result Execution time Memory
991069 2024-06-01T08:19:01 Z User0069 Teams (IOI15_teams) C++17
77 / 100
 662 ms 286936 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,val[maxn*20],r[maxn*20],l[maxn*20],cur;
struct node
{
    node *l,*r;
    int val;
    node():l(NULL),r(NULL),val(0){};
};
int new_node()
{
    return ++cur;
}
int root[maxn];
vector<int> v[maxn];
int cons(int cl,int cr)
{
    int kk=new_node();
    if(cl==cr)
    {
        return kk;
    }
    int mid=(cl+cr)/2;
    l[kk]=cons(cl,mid);
    r[kk]=cons(mid+1,cr);
    return kk;
}
int update(int kk,int cl,int cr,int pos,int v)
{
    int kkk=new_node();
    l[kkk]=l[kk];
    r[kkk]=r[kk];
    val[kkk]=val[kk];
    if(cl==cr)
    {
        val[kkk]+=v;
        return kkk;
    }
    int mid=(cl+cr)/2;
    if(pos<=mid) l[kkk]=update(l[kk],cl,mid,pos,v);
    else r[kkk]=update(r[kk],mid+1,cr,pos,v);
    val[kkk]=val[l[kkk]]+val[r[kkk]];
    return kkk;
}
int get(int kk,int cl,int cr,int L,int R )
{
    if(cl>R||cr<L) return 0;
    if(cl>=L&&cr<=R) return val[kk];
    int mid=(cl+cr)/2;
    return get(l[kk],cl,mid,L,R)+get(r[kk],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(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<m;i++)
    {
        int prev,late,a,b,sum=0;
        a=k[i];
        prev=st.back().a;
        b=prev+1;
        late=(i==m-1)?N+1:k[i+1];
        int ra=k[i]-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,k[i]))<k[i])
        {
            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,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]});
//        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 'int update(int, int, int, int, int)':
teams.cpp:44:45: warning: declaration of 'v' shadows a global declaration [-Wshadow]
   44 | int update(int kk,int cl,int cr,int pos,int v)
      |                                         ~~~~^
teams.cpp:31:13: note: shadowed declaration is here
   31 | vector<int> v[maxn];
      |             ^
teams.cpp: In function 'int32_t can(int32_t, int32_t*)':
teams.cpp:143:13: warning: declaration of 'l' shadows a global declaration [-Wshadow]
  143 |         int l=ra,r=st.back().range,ans=-1;
      |             ^
teams.cpp:19:31: note: shadowed declaration is here
   19 | int N,val[maxn*20],r[maxn*20],l[maxn*20],cur;
      |                               ^
teams.cpp:143:18: warning: declaration of 'r' shadows a global declaration [-Wshadow]
  143 |         int l=ra,r=st.back().range,ans=-1;
      |                  ^
teams.cpp:19:20: note: shadowed declaration is here
   19 | int N,val[maxn*20],r[maxn*20],l[maxn*20],cur;
      |                    ^
teams.cpp:117:18: warning: variable 'late' set but not used [-Wunused-but-set-variable]
  117 |         int prev,late,a,b,sum=0;
      |                  ^~~~

Subtask #1
21.0 / 21.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 43004 KB Output is correct
2 Correct 38 ms 42832 KB Output is correct
3 Correct 35 ms 42832 KB Output is correct
4 Correct 36 ms 43344 KB Output is correct
5 Correct 21 ms 41808 KB Output is correct
6 Correct 21 ms 41820 KB Output is correct
7 Correct 19 ms 41816 KB Output is correct
8 Correct 19 ms 41820 KB Output is correct
9 Correct 37 ms 41684 KB Output is correct
10 Correct 70 ms 41684 KB Output is correct
11 Correct 25 ms 41680 KB Output is correct
12 Correct 20 ms 41684 KB Output is correct
13 Correct 25 ms 41684 KB Output is correct
14 Correct 28 ms 42260 KB Output is correct
15 Correct 35 ms 42836 KB Output is correct
16 Correct 38 ms 42864 KB Output is correct
17 Correct 22 ms 41564 KB Output is correct
18 Correct 22 ms 41564 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 43344 KB Output is correct
2 Correct 42 ms 43356 KB Output is correct
3 Correct 508 ms 46176 KB Output is correct
4 Correct 38 ms 43348 KB Output is correct
5 Correct 399 ms 42068 KB Output is correct
6 Correct 344 ms 42068 KB Output is correct
7 Correct 25 ms 42332 KB Output is correct
8 Correct 267 ms 42068 KB Output is correct
9 Correct 37 ms 41680 KB Output is correct
10 Correct 301 ms 41764 KB Output is correct
11 Correct 347 ms 41928 KB Output is correct
12 Correct 376 ms 42008 KB Output is correct
13 Correct 553 ms 42236 KB Output is correct
14 Correct 662 ms 44632 KB Output is correct
15 Correct 301 ms 43344 KB Output is correct
16 Correct 325 ms 43148 KB Output is correct
17 Correct 239 ms 42320 KB Output is correct
18 Correct 282 ms 42036 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 371 ms 286936 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -